树状数组

void (ll p, ll x){
    for(int i = p; i <= n; i += i & -i)
        sum1[i] += x, sum2[i] += x * p;
}
void range_add(ll l, ll r, ll x){
    add(l, x), add(r + 1, -x);
}
ll ask(ll p){
    ll res = 0;
    for(int i = p; i; i -= i & -i)
        res += (p + 1) * sum1[i] - sum2[i];
    return res;
}
ll range_ask(ll l, ll r){
    return ask(r) - ask(l - 1);
}

 void init(){
        for(int i=1;i<=n;i++){
            c[i]=a[i];
            for(int j=1;j<lb(i);j<<=1)
                c[i]=max(c[i],c[i-j]);
        }
    } 
void update(int x,int s){
        a[x]=s;
        for(;x<=n;x+=lb(x)){
            c[x]=s;
            for(int i=1;i<lb(x);i<<=1)
                c[x]=max(c[x],c[x-i]);
        }
    }

    
int ask(int l,int r){
        int ans=a[r];
        while(1){
            ans=max(ans,a[r]);
            if(l==r) break;
            for(r--;r-lb(r)>=l;r-=lb(r))
                ans=max(ans,c[r]);
        }
        return ans;
    }