题目链接:http://poj.org/problem?id=3468
题意:给出一个数列,两种操作:(1)将区间[L,R]的数字统一加上某个值;(2)查询区间[L,R]的数字之和。
思路:数列A,那么区间[1,x]的和为:
struct BIT { i64 a[N]; void clear() { clr(a,0); } void add(int x,int t) { while(x<N) a[x]+=t,x+=x&-x; } i64 get(int x) { i64 ans=0; while(x) ans+=a[x],x-=x&-x; return ans; } }; BIT a,b; int n,m; i64 p[N]; int main() { Rush(n) { RD(m); int i; FOR1(i,n) RD(p[i]),p[i]+=p[i-1]; a.clear(); b.clear(); char op[10]; int L,R,x; while(m--) { RD(op); if(op[0]=='Q') { RD(L,R); PR(p[R]-p[L-1]+(R+1)*a.get(R)-b.get(R)-L*a.get(L-1)+b.get(L-1)); } else { RD(L,R,x); a.add(L,x); a.add(R+1,-x); b.add(L,x*L); b.add(R+1,-x*(R+1)); } } } }