13. 1726 : 구간의 최대값1

문제 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=999&sca=50&sfl=wr_hit&stx=1726&sop=and

JUNGOL | 구간의 최대값1 > 문제은행

문제 풀이 : 

#include <stdio.h>
#define MAX 50000
int tree[MAX * 3];
int N, Q;
void update(int node, int s, int e, int idx, int data) {
    int m;
    if (s == e) {
        tree[node] = data;
        return;
    }
    m = (s + e) / 2;
    if (idx <= m) update(node * 2, s, m, idx, data);
    else update(node * 2 + 1, m + 1, e, idx, data);
    tree[node] = (tree[node * 2] > tree[node * 2 + 1] ? tree[node * 2] : tree[node * 2 + 1]);
}
int query(int node, int s, int e, int qs, int qe) {
    int m, l, r;
    if (qs <= s && e <= qe) return tree[node];
    else if (qe < s || e < qs) return 0;//범위를 넘어서는 경우
    m = (s + e) / 2;
    l = query(node * 2, s, m, qs, qe);
    r = query(node * 2 + 1, m + 1, e, qs, qe);
    return (l > r) ? l : r;
}
 
int main() {
    int i, data, qs, qe;
    scanf("%d %d", &N, &Q);
    for (i = 1; i <= N; i++) {
        scanf("%d", &data);
        update(1, 1, N, i, data);
    }
    for (i = 1; i <= Q; i++) {
        scanf("%d %d", &qs, &qe);
        printf("%d\n", query(1, 1, N, qs, qe));
    }
}