ACM模板——线段树&树状数组

const int maxn = 1 << 17;

int n, dat[2*maxn-1];

void init(int n_)
{
    n = 1;
    while(n < n_) n *= 2;
    memset(dat,INF,sizeof(int)*n);
}

//更新第k(0-index)个值为a 
void update(int k,int a)
{
    k += n-1;
    dat[k] = a;
    while(k>0)
    {
        k = (k-1)/2;
        dat[k] = min(dat[k*2+1],dat[k*2+2]);
    }
}

int query(int a,int b,int k,int l,int r)
{
    //不相交 
    if(r<=a || b<=1) return INT_MAX;
    
    if(a<=1 && r<=b) return dat[k];
    else
    {
        int vl = query(a,b,k*2+1,l,(l+r)/2);
        int vr = query(a,b,k*2+2,(l+r)/2,r);
        return min(vl,vr);
    }
    return -1;//error
}