segment tree

https://www.acmicpc.net/problem/10167
http://www.spoj.com/problems/KQUERY/
http://codeforces.com/contest/380/problem/C

--
정보
http://codeforces.com/blog/entry/15890
http://codeforces.com/blog/entry/15729

struct SegmentTree{
    int n;
    vector<int> s;
    SegmentTree():n(N),s(N<<2,INT_MAX){}
    void build(int id=1, int l=0, int r=N-1)
    {
        if(r==l){
            s[id] = INT_MAX // or a[l];
            return;
        }
        int mid = (l+r)>>1;
        build(id<<1, l, mid);  
        build(id<<1|1, mid+1, r); 
        s[id] = min(s[id<<1] , s[id<<1|1]);
    }   

    void modify(int p, int x, int id=1, int l=0, int r=N-1)
    {
        s[id] = min(s[id], x);
        if(r==l)return;
        
        int mid = (l+r)>>1;
        if(p <= mid)
            modify(p, x, id<<1, l, mid);
        else
            modify(p, x, id<<1|1, mid+1, r);
    }

    int query(int x, int y, int id=1, int l=0, int r=N-1)
    {
        if(y < l || r < x) return INT_MAX;
        if(x <= l && r <= y) return s[id];
        int mid = (l+r)>>1;
        return min(query(x, y, id<<1, l, mid),
                query(x, y, id<<1|1, mid+1, r));
    }
};