题意：区间更新，输出查询结果
带有延时标记的区间更新
更到你时就停住，用到你时候向下更：（图片来自网络）
我的理解：例如更新[0-3],更新时找到[0-2],[3-3]这两个区间，修改整个区间的信息，如若区间结点的值代表整个区间的最小值，对[0-3]这个区间的操作是每个元素加1，那么更新时只需要修改[0-2]和[3-3]结点的值，两个节点最值加1，并给它们加上标记（它更到这儿就停止了，叶子节点并没有全部加1）。然后区间信息往上合并。这样实际上下面的信息并没有全部更新（[0-2]的所有子孙结点）。当我们需要下面的信息时，如需要[0-1]区间的信息，进行查询时，发现[0-2]区间有标记，然后更新其子结点信息，并加上标记。
#include<cstdio> #include<cstring> #define ll long long using namespace std; const int maxn = 1e5+10; struct segtree { int l,r; ll sum; ll mark; }node[4*maxn]; int a[maxn]; void pushdown(int r) { if(node[r].mark!=0) { node[r*2+1].sum+=(node[r*2+1].r-node[r*2+1].l+1)*node[r].mark; node[r*2+2].sum+=(node[r*2+2].r-node[r*2+2].l+1)*node[r].mark; node[r*2+1].mark+=node[r].mark; node[r*2+2].mark+=node[r].mark; node[r].mark=0; } } void build(int r,int s,int e) { node[r].mark=0; node[r].l=s; node[r].r=e; if(s==e) { node[r].sum=a[s]; return; } int mid=(s+e)/2; build(r*2+1,s,mid); build(r*2+2,mid+1,e); node[r].sum=node[r*2+1].sum+node[r*2+2].sum; } ll query(int r,int qs,int qe) { int s=node[r].l; int e=node[r].r; if(qe<s||qs>e)return 0; if(qs<=s&&qe>=e)return node[r].sum; pushdown(r); int mid=(s+e)/2; if(qe<=mid) return query(r*2+1,qs,qe); else if(qs>mid) return query(r*2+2,qs,qe); else { return query(r*2+1,qs,qe)+ query(r*2+2,qs,qe); } } void update(int r,int us,int ue,int delta) { int s=node[r].l; int e=node[r].r; if(us>e||ue<s)return; if(us<=s&&ue>=e) { int n=e-s+1; node[r].mark+=delta; node[r].sum += n*delta; return; } pushdown(r); int mid=(s+e)/2; if(ue<=mid) update(r*2+1,us,ue,delta); else if(us>mid) update(r*2+2,us,ue,delta); else { update(r*2+1,us,ue,delta); update(r*2+2,us,ue,delta); } node[r].sum=node[r*2+1].sum+node[r*2+2].sum; } int main() { int n,qnum; //freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&qnum)) { for(int i=1;i<=n;i++)scanf("%d",&a[i]); build(0,1,n); char cmd[2]; int a,b,c; while(qnum--) { scanf("%s",&cmd); if(cmd[0]=='Q') { scanf("%d%d",&a,&b); printf("%lld\n",query(0,a,b)); } else { scanf("%d%d%d",&a,&b,&c); update(0,a,b,c); } } } }
