题干：
给定长度为N（N<=105)的数列A，然后输入Q（Q<=105）行操作指令。
第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。
第二类指令形如“Q l r”，表示询问数列中第l~r个数的和。
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
思路：在 A Tiny Problem with Integers这篇博文中，我们用树状数组维护了一个数组b，对于每条指令“C l r d”，把b[l]加上d，b[r+1]减去d。b数组的前缀和就是经过这些指令后a[x]增加的值。
那么序列a的前缀和a[1~x],整体增加的值就是：
上式可以改写为
解释一下公式是怎么来的
i=1 b[1]
i=2 b[1]+b[2]
i=3 b[1]+b[2]+b[3]
i=4 b[1]+b[2]+b[3]+b[4]
……
i=x b[1]+b[2]+b[3]+b[4]+……+b[x]
把每行都加起来我们发现有x个b[1],x-1个b[2],x-2个b[3],x-3个b[4]……有一个b[x]
我们把每行竖着加起来，也就是x个b[1]加起来，x-1个b[2]加起来……，
如下图
我们看一下第二个公式的其中一部分，和上述列相加是吻合的
当i=1时 x-i+1=x-1+1=x，有个x个b[1]
当i=2时 x-i+1=x-2+1=x-1，有x-1个b[2]
当i=3时 x-i+1=x-3+1=x-2，有x-2个b[3]
……
当i=x时 x-i+1=x-x+1=1，有1个b[x]
我们来看第二个公式的最后一部分
先把第二公式的第二部分拆分成两部分
再把
用乘法分配律，变成先后乘，如下图
这是第二个公式的推导过程。
值得指出的是，我们把第一个公式变成第二公式，把两个变量i，j的变化转化成了就依赖于一个变量i变化，这其实就是一个优化。
我们把
转化为
的原因是我们前缀和只能维护b[i],在修改时无法确定（x-i+1）的值。
分离包含多个变量的项，使公式中不同变量之间互相独立的思想非常重要，以后讨论动态规划的优化策略时会多次用到
代码实现：
在本题中，我们增加一个树状数组，用于维护ib[i]的前缀和
上式就可以直接计算，查询了。
具体来说，我们建立两个树状数组c0和c1，起初全部赋值为0.对于每条指令“C l r d”,执行4个操作
1、在树状数组c0中，把位置l上的数加d
2、在树状数组c0中，把位置r+1上的数减d
3、在树状数组c1中，把位置l上的数加ld
4、咋树状数组c1中，把位置r+1上的数减（r+1）*d
另外，我们建立数组sum存储序列a的元素前缀和，对于每条指令
“Q l r”
当然还是拆成1~r 和 1~l-1两部分，二者相减。写成式子就是
(sum[r] +[(r+1)*ask(c0,r)-ask(c1,r))-(sum[l-1]+(l-1)*ask(c0,l-1)-ask(c1,l-1))
完整代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZE=100010;
int a[SIZE],n,m;
long long c[2][SIZE],sum[SIZE];
long long ask(int k,int x)
{
long long ans=0;
for(;x;x-=x&-x) ans+=c[k][x];
return ans;
}
void add(int k,int x,int y)
{
for(;x<=n;x+=x&-x) c[k][x]+=y;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
while(m--)
{
char op[2]; int l,r,d;
scanf("%s%d%d",op,&l,&r);
if(op[0]=='C')
{
scanf("%d",&d);
add(0,l,d);
add(0,r+1,-d);
add(1,l,l*d);
add(1,r+1,-(r+1)*d);
}
else{
long long ans=sum[r]+(r+1)*ask(0,r)-ask(1,r);
ans-=sum[l-1]+l*ask(0,l-1)-ask(1,l-1);
printf("%lld\n",ans);
}
}
}