树状数组的基本用途是维护前缀和 x的二进制分解为2i1+2i2…2im 设i1为最高位 区间[1,x]可以分为: 1.长度为2i1的区间[1,2i1]， 2.长度为2i2的区间[2i1+1,2i1+2i2] … m.长度为2im的区间和[2i1+2i2…2im-1+1,2im]
假设区间[l,r]区间的结尾为r，则区间长度为r的二进制最后以为对应的数 据此用c[x]表示[x-lowbit(x)+1,x]间的和
取二进制最后一位1对应的数
int lowbit(int x){ return x&-x; }原理： -x操作是对x取反加1 例如01101000取反之后就是10010111，再加1就变成10011000 01101000和10011000与操作&之后就是00001000，也就是原来的数最后一位二进制1对应的数
1.直接用单点修改函数add初始化 2.根据c[i]的性质用前缀和高效初始化 3.如果是在差分数组上操作还能利用差分数组的性质更高效初始化
for(int i=1;i<=n;i++){//add函数初始化 cin>>a[i]; add(i,a[i]); } for(int i=1;i<=n;i++){//前缀和初始化 cin>>a[i]; sum[i]=sum[i-1]+a[i]; c[i]=sum[i]-sum[i-lowbit(i)]; } for(int i=1;i<=n;i++){//差分数组才能用哦,因为差分数组的前缀和就是元素本身 cin>>a[i];//也可以先求出差分数组然后再用add c[i]=a[i]-a[i-lowbit(i)]; }1.树状数组维护差分数组前缀和，差分数组的前缀和即为元素本身 2.利用差分数组的性质高效进行区间修改：add(l,x)+add(r+1,-1)
区间查询要用到前缀和，是树状数组的基本操作 但是区间修改要用差分数组 假设树状数组c[]维护的是差分数组d[]的前缀和，则： a[1]+a[2]+……+a[x] = c[1]+(c[1]+c[2])+(c[1]+c[2]+c[3])+……+(c[1]+c[2]+……+c[x]) = x* (c[1]+c[2]+……+c[x])-(0* c[1]+1* c[2]+2* c[3]+…+(x-1)* c[x]) = x* (c[1]+c[2]+……+c[x])-∑(i-1)* c[i]
结果的左边c[1]+c[2]+……+c[x]直接就能维护，用的时候乘上x就行了 而后面的∑(i-1)*c[i]，新建一个数组c2[i] = (i-1)*c[i]，在修改c1的也修改c2。 例如： 对区间[l,r]增加x是对c1:add(l,x),add(r+1,-x) 则我们同时需要对c2数组的l 和r+1两个点修改：add(l,(l-1)*x),add(r+1,-r *x)
区间查询和之前差不多，只是多了一个数组： (r*ask(0,r)-ask(1,r))-((l-1)*ask(0,l-1)-ask(1,l-1))
详细代码参考：
区间修改+区间查询
#include<iostream> #include<cstdio> #define lowbit(x) ((x)&(-(x))) #define ll long long using namespace std; const int maxm=1e5+5; ll a[maxm]; ll c[2][maxm]; int n,m; void add(int k,int i,int x){ for(;i<=n;i+=lowbit(i)){ c[k][i]+=x; } } ll ask(int k,int i){ ll ans=0; for(;i;i-=lowbit(i)){ ans+=c[k][i]; } return ans; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; add(0,i,a[i]-a[i-1]); add(1,i,(i-1)*(a[i]-a[i-1])); } while(m--){ int d; cin>>d; if(d==1){ int l,r,x; cin>>l>>r>>x; add(0,l,x); add(0,r+1,-x); add(1,l,(l-1)*x); add(1,r+1,-r*x); }else{ int l,r; cin>>l>>r; cout<<(r*ask(0,r)-ask(1,r))-((l-1)*ask(0,l-1)-ask(1,l-1))<<endl; } } return 0; }待续
