» » RMQ with Segment Tree

RMQ with Segment Tree

   2:43 AM       

#define mx 1000010
#define tmx 2000020

int a[mx];
int t[tmx];
void init(int node, int i, int j){
    if(i==j){
        t[node] = a[i];
        return;
    }
    int mid = (i+j)>> 1;
    init(2*node, i, mid);
    init((2*node)+1, mid+1, j);
    t[node] = max(t[2*node], t[(2*node)+1]);
}
int query(int node, int i, int j, int si, int sj){
    if(i == si && j == sj)return t[node];
    int mid = (i+j)>> 1;
    if(sj <= mid)return query(2*node, i, mid, si, sj);
    else if(si > mid)return query((2*node)+1, mid+1, j, si, sj);
    else{
        int r1 = query(2*node, i, mid, si, mid);
        int r2 = query((2*node)+1, mid+1, j, mid+1, sj);
        return max(r1,r2);
    }
}
void update(int node, int i, int j, int idx, int val){
    if(i == j){
        a[i] = val;
        t[node] = val;
        return;
    }
    int mid = (i+j)>> 1;
    if(idx <= mid) update(2*node, i, mid, idx, val);
    else update ((2*node)+1, mid+1, j, idx, val);
    t[node] = max(t[2*node], t[(2*node)+1]);
}