1、附上题目题目描述给你一个包含N个整数的数列：A1, A2, ... , AN。你需要来完成两种操作：1、对于一个区间的每个数字加上某个数值；2、询问一个区间的数字之和。输入1行：两个数字N和Q。1 ≤ N,Q ≤ 100000。2行：包含N个整数，初始值为A1, A2, ... , AN。-1000000000 ≤ Ai ≤ 1000000000。接下来Q行，每行表示一个操作。"C a b c" 表示 Aa, Aa+1, ... , Ab中每个数，加上c。 -10000 ≤ c ≤ 10000。"Q a b" 表示询问 Aa, Aa+1, ... , Ab的和。输出你需要输出每个查询操作的结果，每个回答一行。
2、建树并将树上节点定为初始值，这个过程比较简单，主要是深搜，代码如下struct tree{ int left,right,value;}s[maxn];void build(int i,int left,int right){ s[i].left=left; s[i].right=right; if(left==right) { s[i].value=a[left];//a是这个节点的权值 return ; } build(i*2,left,(left+right)/2); build(i*2+1,(left+right)/2+1,right); s[i].value=s[i*2].value+s[i*2+1].value;}
3、第二，就是求和了，这里用的方法是每个点加一个add值，代表这个节点的所有叶节点的值都要加上add，而足饶戽沸每次往下深搜时，将此节点的add值更新到两个叶子节点上，并将原来这个节点的权值更新。这点学到后面非常重要。void que(int i,int lef,int rig){ if(s[i].add!=0) { s[i].value+=s[i].add*(s[i].right-s[i].left+1); s[2*i].add+=s[i].add; s[2*i+1].add+=s[i].add; s[i].add=0； } if(s[i].left>=lef && s[i].right<=rig) { sum+=s[i].value; return ; } int kk=i*2; if(s[kk].right>=lef)que(kk,lef,rig); if(s[kk+1].left<=rig)que(kk+1,lef,rig);//不断往下深搜}
4、第三，区间更新，如果当前搜索到的节点被包含在你要修改的区间中，就将此节点的add值更新。void addtree(int i,i荏鱿胫协nt val,int lef,int rig){ if(s[i].left>=lef && s[i].right<=rig) { s[i].add+=val; return ; } if(lef>=s[i].left && rig<=s[i].right)s[i].value+=val*(rig-lef+1); else s[i].value+=val*(min(abs(s[i].right-lef+1),abs(rig-s[i].left+1))); if(s[i].add!=0) { s[i].value+=(s[i].right-s[i].left+1)*s[i].add; s[2*i].add+=s[i].add; s[2*i+1].add+=s[i].add;s[i].add=0; } int kk=2*i; if(s[kk].right>=lef)addtree(kk,val,lef,rig); if(s[kk+1].left<=rig)addtree(kk+1,val,lef,rig);}
5、最后附上源代码#include<iostream>#include<cstdio>#include<cmat茑霁酌绡h>using namespace std;struct tree{int left,right;long long value,add;}s[1000001];//int fa[100001];int n,q;long long sum,a[100001];void build(int i,int left,int right){s[i].left=left;s[i].right=right;if(left==right){s[i].value=a[left];return ;}build(i*2,left,(left+right)/2);build(i*2+1,(left+right)/2+1,right);s[i].value=s[i*2].value+s[i*2+1].value;}void que(int i,int lef,int rig){if(s[i].add!=0){s[i].value+=s[i].add*(s[i].right-s[i].left+1);s[2*i].add+=s[i].add;s[2*i+1].add+=s[i].add;s[i].add=0;//s[2*i].value+=(s[2*i].right-s[2*i].left+1)*s[2*i].add;//s[2*i+1].value+=(s[2*i+1].right-s[2*i+1].left+1)*s[2*i+1].add;}if(s[i].left>=lef && s[i].right<=rig){sum+=s[i].value;return ;}int kk=i*2;if(s[kk].right>=lef)que(kk,lef,rig);if(s[kk+1].left<=rig)que(kk+1,lef,rig);}void addtree(int i,int val,int lef,int rig){if(s[i].left>=lef && s[i].right<=rig){s[i].add+=val;//s[i].value=s[i].value+s[i].add*(s[i].right-s[i].left+1);return ;}if(lef>=s[i].left && rig<=s[i].right)s[i].value+=val*(rig-lef+1);else s[i].value+=val*(min(abs(s[i].right-lef+1),abs(rig-s[i].left+1)));if(s[i].add!=0){s[i].value+=(s[i].right-s[i].left+1)*s[i].add;s[2*i].add+=s[i].add;s[2*i+1].add+=s[i].add;s[i].add=0;//s[2*i].value+=(s[2*i].right-s[2*i].left+1)*s[2*i].add;//s[2*i+1].value+=(s[2*i+1].right-s[2*i+1].left+1)*s[2*i+1].add;}int kk=2*i;if(s[kk].right>=lef)addtree(kk,val,lef,rig);if(s[kk+1].left<=rig)addtree(kk+1,val,lef,rig);}int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);for(int i=1;i<=q;i++){char k;cin>>k;if(k=='C'){int d;int b,c;scanf("%d%d%d",&b,&c,&d);addtree(1,d,b,c);}if(k=='Q'){int b,c;scanf("%d%d",&b,&c);sum=0;que(1,b,c);printf("%lld\n",sum);}}}
