线段树

#define e tree[id]
#define lson tree[id*2]
#define rson tree[id*2+1]
const int maxn = 10005;

struct Tree{
    int le,ri,v;
}tree[4*maxn];

void pushup(int id){
    e.v = max(lson.v,rson.v);
} 

void Build_tree(int id,int le,int ri)
{
    e.le=le,e.ri=ri;
    if(le==ri)
    {
        e.v=A[le];
        return ;    
    }    
    int mid=(le+ri)/2;
    Build_tree(id*2,le,mid);
    Build_tree(id*2+1,mid+1,ri);
    pushup(id);//类似回溯，根据左右子树的值修改 
}

int Query(int id,int x,int y)
{
    int le=e.le,ri=e.ri;
    if(x<=le && ri<=y) return e.v;
    int mid=(le+ri)/2;
    int ret = -INF;
    if(x<=mid) ret=max(ret,Query(id*2,x,y);
    if(y>mid) ret =max(ret,Query(id*2+1,x,y));
    return ret;
} 
//单点更新 
void Update(int id,int k,int v)
{
    int le=e.le,ri=e.ri;
    if(le==ri)
    {
        e.v=v;
        return ;
    }
    int mid=(le+ri)/2;
    if(k<=mid) Update(id*2,k,v);
    else Update(id*2+1,k,v);
    pushup(id);//容易忘记 
}
//成段更新
void pushdown(int id,int x,int y)
{
    int le=e.le,ri=e.ri;
    if(e.d!=0 && le!=ri) 
    {
         lson.v+=d;
         rson.v+=d;
         lson.d+=d;
         rson.d+=d;
         e.d=0;
         return ; 
    }    
} 
void Update(int id,int x,int y,int d)
{
    int le=e.le,ri=e.ri;
    if(x<=le && ri<=y)
    {
        e.v+=d;
        e.d+=d;
        return ;
    }
    pushdown(id);
    int mid=(le+ri)/2;
    if(x<=mid) Update(id*2,x,y,d);
    if(y>mid) Update(id*2+1,x,y,d);
    pushup(id); 
}