题意：有一个数组，需要进行区间查询和区间更新的操作，N个数，Q次询问，询问时输出结果。
想法：可以用线段树，但这里是用树状数组的区间更新和区间查询操作。
这里主要解决树状数组的一些问题：为什么树状数组可以进行单点更新，区间查询；区间更新，单点查询。为什么树状数组不可以直接进行区间更新，区间查询？
原因：区间更新，我们只能得到这个区间内的整体变化（换句话来说，区间更新表示区间内点改变量的总值，但是变了几个点，哪几个点变了我们却不得而知），点更新，可以知道是一个确定点的变化。那么为什么用了区间更新，不可以进行区间查询呢？因为更新的区间内每个点的情况不确定，当进行区间查询的时候需要去除一些点，所以不知道哪些点是有用的，哪些点是无用的，所以只能得到A1-Ak的和，却不能够得到An-Am（n，m不等于1）。所以，当点更新时，表明已经明确了，哪些点被增加了值，所以允许进行区间查询，那么是不是就一定不能够，完成，区间更新，区间查询了吗？显然不是，下面介绍一种方法。
求：M[n] = A[1] + A[2] + A[3] + ...... + A[n]
设arrPlus[i] = A[i] - A[i-1];
则M[n] = arrPlus[1] + (arrPlus[2] + arrPlus[1]) + (arrPlus[3] + arrPlus[2] + arrPlus[1]) + ...... +(arrPlus[n] + arrPlus[n-1] + ...... + arrPlus[1])
得M[n] = n*(arrPlus[1] + arrPlus[2] + ...... + arrPlus[n]) - (0*arrPlus[1] + 1*arrPlus[2] + 2*arrPlus[3] + ...... + (n-1)*arrPlus[n])
设arrPlusC = (i-1)*arrPlus[i]
那么此时就变成了维护arrPlus数组和arrPlusC数组了，通过区间更新，点查询，从而得到M，对于题目中的区间查询[a,b]，可由M[b]-M[a-1]得到。
#include<iostream> #include<cstring> #include<cstdio> #define ll long long using namespace std; const int maxN=100000+50; ll org[maxN]; ll arrBitK[maxN],arrBitKK[maxN]; ll sumK[maxN],sumKK[maxN],CplusK[maxN],CplusKK[maxN]; int N,Q; int LowBit(int x) { return x&(-x); } ll BitGetSum(ll* arrBit,int pos) { ll sum=0; while(pos) { sum+=arrBit[pos]; pos-=LowBit(pos); } return sum; } void BitAdd(ll* arrBit,int pos,ll val) { while(pos<=N) { arrBit[pos]+=val; pos+=LowBit(pos); } } void Init() { memset(sumK,0,sizeof(sumK)); memset(sumKK,0,sizeof(sumKK)); memset(arrBitK,0,sizeof(arrBitK)); memset(arrBitKK,0,sizeof(arrBitKK)); } ll GetM(int pos) { ll k1=pos*sumK[pos]-sumKK[pos]; ll k2K=pos*BitGetSum(arrBitK,pos); ll k2KK=BitGetSum(arrBitKK,pos); return k1+k2K-k2KK; } int main() { while(cin>>N>>Q) { Init(); for(int i=1;i<=N;i++) { cin>>org[i]; } org[0]=0; for(int i=1;i<=N;i++) { CplusK[i]=org[i]-org[i-1]; CplusKK[i]=CplusK[i]*(i-1); } for(int i=1;i<=N;i++) { sumK[i]=sumK[i-1]+CplusK[i]; sumKK[i]=sumKK[i-1]+CplusKK[i]; } for(int i=1;i<=Q;i++) { char way[5]; int a,b,c; cin>>way; if(way[0]=='Q') { cin>>a>>b; cout<<GetM(b)-GetM(a-1)<<endl; } else { cin>>a>>b>>c; BitAdd(arrBitK,a,c); BitAdd(arrBitK,b+1,-c); BitAdd(arrBitKK,a,c*(a-1)); BitAdd(arrBitKK,b+1,(-c)*b); } } } return 0; }
