题目是对一个数组，支持两种操作
操作C：对下标从a到b的每个元素，值增加c；
操作Q：对求下标从a到b的元素值之和。
这道题也可以用线段树解，本文不做描述，下面分析如何用树状数组来解决这道题。
先把问题简化一点，因为 结果=初值+增量，所以，我们可以只对增量进行分析。然后，这种题有一个特点，就是如果对一般的一个操作C与操作查询前缀和的组合符合条件，那么无论进行多少次任意操作结果都是正确的。故 假设，先进行一次参数分别为 l,r,c 的操作C，再进行一次查询前缀和Si的操作(i 与l r的大小关系不定）。操作C之后，对Si，①当i<l时，Si=0，②当l<=i<r时，Si=c*(i-l+1)，③当i>=r时，Si=c*(r-l+1)。要使情况①③满足比较简单，只需使add操作不在l左边进行，且对一树状数组的l和r分别进行+x+c*(r-l+1),-x的操作；而分析如何满足情况②，可以把Si看作是分布在直线y=c(x-l)=cx-cl上的一系列散点，易看出实现+cx的方法，就是在l执行add c的操作，在r执行add -c的操作，查询时查询sum()*x，而实现-cl的方法可以与上面“分别进行+x+c*(r-l+1),-x的操作”（引号中的x是不确定的）联系起来得出。故而任意Si都可以得出。
题目链接： http://poj.org/problem?id=3468
1 #include <cstdio> 2 3 typedef long long LL; 4 5 const int maxn =1e5+5; 6 LL a[2][maxn]; 7 LL psum[maxn]; 8 int n; 9 10 inline int lowbit(int x) 11 { 12 return x&-x; 13 } 14 void add(LL a[],int x,int d) 15 { 16 while(x<=n) 17 { 18 a[x]+=d; 19 x+=lowbit(x); 20 } 21 } 22 LL sum(LL a[],int x) 23 { 24 LL ret=0; 25 while(x) 26 { 27 ret+=a[x]; 28 x-=lowbit(x); 29 } 30 return ret; 31 } 32 33 LL query(int x) 34 { 35 return sum(a[1],x)*x+sum(a[0],x); 36 } 37 38 int main() 39 { 40 int q; 41 scanf("%d%d",&n,&q); 42 for(int i=1;i<=n;i++) 43 { 44 scanf("%I64d",&psum[i]); 45 psum[i]+=psum[i-1]; 46 } 47 char op[3]; 48 while(q--) 49 { 50 int l,r; 51 scanf("%s%d%d",op,&l,&r); 52 if(op[0]==‘Q‘) 53 printf("%I64d\n",query(r)-query(l-1)+psum[r]-psum[l-1]); 54 else 55 { 56 int c; 57 scanf("%d",&c); 58 add(a[1],l,c); 59 add(a[1],r,-c); 60 add(a[0],l,c*(-l+1)); 61 add(a[0],r,c*r); 62 } 63 } 64 }
POJ_3468: A Simple Problem with Integers （树状数组区间更新）
原文：http://www.cnblogs.com/Just--Do--It/p/6351890.html