线段数的查询和修改都是logn的。

struct node{int l,r;int v;
}tr[N*4];//经验值*4void pushup(int u)
{tr[u].v=max(tr[u<<1].v,tr[u<<1+1].v);
}
void built(int u,int l,int r)
{tr[u]={l,r};if(l==r) return;int mid=l+r>>1;	built(u<<1,l,mid);//建树时候这里是midbuilt(u<<1+1,mid+1,r);	
}int query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;int mid=tr[u].l+tr[u].r>>1;int v=0;if(l<=mid) v=query(u<<1,l,r);//注意这里依旧是查询l，rif(r>mid) v=max(v,query(u<<1+1,l,r));
}
void modify(int u,int x,int v)
{if(tr[u].l==x&&tr[u].r==x) tr[u].v=v;else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1+1,x,v);pushup(u);		}}

区间修改，区间查询（pushdown操作）

pushdown操作的定义为，给该区间的子区间，每个区间加上一些东西。

由于pushdown有延时性，所以每次在query或者modify时应该先pushdown操作一下

#include<bits/stdc++.h>using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int g[N];
struct node{int l,r;LL sum,add;
}tr[N*4];int n,m;
void pushup(int u)
{tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];if(root.add){left.add+=root.add,left.sum+=(LL)(left.r-left.l+1)*root.add;right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;root.add=0;}
}
void built(int u,int l,int r)
{if(l==r) tr[u]={l,r,g[r],0};else{tr[u]={l,r};int mid=l+r>>1;built(u<<1,l,mid);built(u<<1|1,mid+1,r);pushup(u);}
}
void modify(int u,int l,int r,int d)
{if(tr[u].l>=l&&tr[u].r<=r){tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;tr[u].add+=d;}else{pushdown(u);//注意这里的pushdown操作int mid=tr[u].r+tr[u].l>>1;if(l<=mid) modify(u<<1,l,r,d);if(r>mid) modify(u<<1|1,l,r,d);pushup(u);}
}
LL query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;pushdown(u);//注意这里的pushdown操作int mid=tr[u].l+tr[u].r>>1;LL sum=0;if(l<=mid) sum=query(u<<1,l,r);if(r>mid) sum+=(LL)query(u<<1|1,l,r);return sum;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>g[i];built(1,1,n);char op[2];int l,r,d;while(m--){cin>>op>>l>>r;if(*op=='Q'){cout<<query(1,l,r)<<endl;}else{cin>>d;modify(1,l,r,d);}}return 0;
}