You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. “C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000. “Q a b” means querying the sum of Aa, Aa+1, … , Ab.
Output You need to answer all Q commands in order. One answer in a line.
Sample Input 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 Sample Output 4 55 9 15 Hint The sums may exceed the range of 32-bit integers.
线段树懒惰标记的板子 延迟标记：每个节点新增加一个标记，记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。
现在可以自己打出来了
#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> using namespace std; typedef long long ll; ll tree[5000002],lazy[5000002]; void build(int l,int r,int rt) { lazy[rt]=0; if(l==r) { scanf("%lld",&tree[rt]); return; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } void pushdown(int rt,int m) { if(lazy[rt]) { lazy[rt<<1]+=lazy[rt];//因为孩子节点可能被多次延迟标记又没有向下传递 lazy[rt<<1|1]+=lazy[rt]; tree[rt<<1]+=(ll)(m-(m>>1))*lazy[rt]; tree[rt<<1|1]+=(ll)(m>>1)*lazy[rt]; lazy[rt]=0;//释放懒惰标记 } } void update(int L,int R,int rt,int l,int r,int val) { if(L>=l&&R<=r) { tree[rt]+=(R-L+1)*val;//更新总和 lazy[rt]+=val;//更新懒惰状态 return; } pushdown(rt,R-L+1);//数据下沉 int mid=(R+L)>>1; if(l<=mid) update(L,mid,rt<<1,l,r,val); if(r>mid) update(mid+1,R,rt<<1|1,l,r,val); tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } ll qurey(int L,int R,int rt,int l,int r) { if(L>=l&&R<=r) { return tree[rt]; } pushdown(rt,R-L+1); int mid=(R+L)>>1; ll ans=0; if(l<=mid) ans+=qurey(L,mid,rt<<1,l,r); if(r>mid) ans+=qurey(mid+1,R,rt<<1|1,l,r); return ans; } int main() { int n,q; while(~scanf("%d%d",&n,&q)) { build(1,n,1); char ch; int a,b,c; while(q--) { cin>>ch; if(ch=='Q') { cin>>a>>b; printf("%lld\n",qurey(1,n,1,a,b)); } else { cin>>a>>b>>c; update(1,n,1,a,b,c); } } } return 0; } #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #define ll long long using namespace std; const int N=1e5+10; ll c1[N],c2[N],a[N]; int n,q; int lowbit(int x) { return (x&-x); } void add1(int x,ll v) { for (;x<=n;x+=lowbit(x)) c1[x]+=v; } void add2(int x,ll v) { for (;x<=n;x+=lowbit(x)) c2[x]+=v; } ll Ask(int x) { ll ans = 0; for (int i = x;i;i-=lowbit(i)) ans+=x*c1[i]-c2[i]; return ans; } int main() { while (~scanf("%d%d",&n,&q)) { memset(c1, 0, sizeof(c1)); memset(c2, 0, sizeof(c2)); for (int i = 1; i <= n; i++) { scanf("%lld",&a[i]); add1(i,a[i]-a[i-1]); add2(i,(i-1)*(a[i]-a[i-1])); } for (int i=1;i<=q;i++) { char c; cin>>c; if (c == 'Q') { int l, r; scanf("%d%d",&l,&r); printf("%lld\n",Ask(r)-Ask(l-1)); } else { int l, r; ll v; scanf("%d%d%lld",&l,&r,&v); add1(l,v); add1(r+1,-v); add2(l,(l-1)*v); add2(r+1,r*(-v)); } } } return 0; }