PROG-1147: Segment Tree

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
int n;
int tree[2*(1<<19)]; // n = 262144 = 2^18 -> ประกาศ [2 * (n+1)]

int update(int i, int l, int r, int pos, int val){
    if(l == r)
        return tree[i] = val;
    int mid = (l + r)/ 2;
    if(pos <= mid)
        return tree[i] = max(update(2*i, l, mid, pos, val), tree[2*i+1]);
    return tree[i] = max(tree[2*i], update(2*i+1, mid+1, r, pos, val));
}

int query(int i, int l, int r, int s, int e){
    if(r < s or l > e)
        return -INF;
    if(s <= l and r <= e)
        return tree[i];
    int mid = (l + r)/ 2;
    return max(query(2*i, l, mid, s, e), query(2*i+1, mid+1, r, s, e)); // ระวัง ห้ามเก็บลง tree[i]
}

int main(){

    int q;
    scanf("%d%d", &n, &q);

    while(q--){
        char a;
        scanf(" %c", &a);
        int x, y;
        scanf("%d%d", &x, &y);
        if(a == 'U')
            update(1, 1, n, x, y);
        else
            printf("%d\n", query(1, 1, n, x, y));
    }

    return 0;
}