线段树模板

int Max[MAXN];      //子区间中的最大值
int ql,qr,p,v;
//ql：查询左边界，qr：查询右边界,p：更新点 v：更新值

//建立线段树
void build(int r,int L,int R)
{
    //如果到了叶节点（区间长度为1），最大值当然是叶节点值；
    if(L==R) scanf("%d",Max+r);
    else
    {
        int M = (L+R)/2;        
        build(r*2,L,M);         //递归建立左子树
        build(r*2+1,M+1,R);    //递归建立右子树
        Max[r] = max(Max[r*2],Max[r*2+1]);  //将左右子区间的最大值更新到根节点
        
    }
}
//对线段树进行查询操作
int query(int r,int L,int R)
{
    int ans = -1;
    int M = (L+R)/2;
    
    //如果该区间在所在查询区间内，那么返回改区间节点的最大值
    if(ql<=L&&R<=qr)
        return Max[r];
    //如果右边界小于中间值，那么所要查询区间一定在左子区间
    if(qr<=M)
        return query(r*2,L,M);
    //如果左边界大于中间值，那么所要查询区间一定在右子区间
    else if(ql>M)
        return query(r*2+1,M+1,R);
    //除了以上两种情况可能的是左边界和右边界跨越两个子区间
    //那么返回两个子区间的最大值
    else
        ans = max(query(r*2,L,M),query(r*2+1,M+1,R));
    return ans;
}
//更新线段树
void update(int r,int L,int R)
{
   int M = (L+R)/2;
   
   //查到更新点，更新值
   if(L==R) Max[r] = v;
   else
   {
       //如果更新点小于中间值，递归更新左子区间
       if(p<=M)
        update(r*2,L,M);
        
        //否则递归更新右子区间
       else
        udapte(r*2+1,M+1,R);
        
        //更新根节点
       Max[r] = max(Max[r*2],Max[r*2+1]);
   }
}