http://poj.org/problem?id=3468 (题目链接)
题意
给出一个序列，要求维护区间修改与区间求和操作。
Solution
多年以前学习的树状数组区间修改又忘记了→_→。
其实就是用树状数组维护一个差分序列${delta[i]}$，${delta[x]}$记录${[i,n]}$中每一个数的增量，每次修改${[l,r]}$就转化为了${delta[l]+=d,delta[r+1]-=d}$。
对于求和操作${[l,r]}$，其实就是${sum(x)-sum(y)}$，我们这里只讨论${sum(x)}$的求法。
$${sum(x)=s[x]+delta[1]*x+delta[2]*(x-1)+delta[3]*(x-2)+······+delta[x]}$$
其中${s[x]}$表示原数组的前缀和。
$${sum(x)=s[x]+\sum_{i=1}^{x}{delta[i]*(x-i+1)}}$$
$${sum(x)=s[x]+(x+1)*\sum_{i=1}^{x}{delta[i]}-\sum_{i=1}^{x}{i*delta[i]}}$$
于是我们用两个树状数组维护${delta[i]}$与${delta[i]*i}$即可。
细节
更新与求和的时候的下标一定不要打错，没注意到，贡献1Wa→_→。
代码
// poj3468
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define MOD 100000000
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
LL c1[maxn],c2[maxn],s[maxn];
int n,m; int lowbit(int x) {return x&-x;}
LL query(int x) {
LL res=0;
for (int i=x;i;i-=lowbit(i)) res+=(x+1)*c1[i]-c2[i]; //important
return res;
}
void add(int x,LL val) {
for (int i=x;i<=n;i+=lowbit(i)) c1[i]+=val,c2[i]+=(LL)val*x;
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",&s[i]),s[i]+=s[i-1];
char ch[10];
for (int x,y,i=1;i<=m;i++) {
scanf("%s%d%d",ch,&x,&y);
if (ch[0]=='Q') printf("%lld\n",s[y]-s[x-1]+query(y)-query(x-1));
else {
LL z;
scanf("%lld",&z);
add(x,z);add(y+1,-z);
}
}
return 0;
}