1.区间整体加一个数，单点求： 已经很常用的方法了，就当成有多少线段覆盖，对a[l,r]k的操作转化为对辅助数组b[l]k,b[r1]-k，树状数组维护b[i]前缀和就好…… 具体来说，是对a[i]差分后生成新数组b[i]，使得b[i]=a[i]-a[i-1]，这样成段修改时： 对il或ir1，a
1.区间整体加一个数，单点求值：
已经很常用的方法了，就当成有多少线段覆盖，对a[l,r]+k的操作转化为对辅助数组b[l]+k,b[r+1]-k，树状数组维护b[i]前缀和就好……
具体来说，是对a[i]差分后生成新数组b[i]，使得b[i]=a[i]-a[i-1]，这样成段修改时：
对ir+1，a[i]值不变故b[i]不变；l<i<r+1又有b[i]=(a[i]+k)-(a[i+1]+k)还是不变。
但b[l]’=(a[l]+k)-a[l-1]=b[l]+k；b[r+1]’=a[r+1]-(a[r]+k)=b[r+本文来源gaodai#ma#com搞*!代#%^码$网!1]-k。
同时对b[i]求前缀和会发现：
sum(p)=b[1]+b[2]+…+b[p]=(a[1]-a[0])+(a[2]-a[1])+…+(b[p]-b[p-1])=a[p]-a[0]=a[p]
这样单点求值的方式也出来了，上代码（套用了下原始的BIT）：
struct BIT_ex { BIT t; void init(int s) {t.init(s);} void change(int l, int r, _int k) {t.change(l,k); t.change(r+1,-k);} _int get(int p) {return t.sum(p);}};
2.区间整体加一个数，求区间和（前缀和）：
好像不是很常见，普及推广一下……
区间整体的修改已经搞出来，肯定是要继续用结论了……
上面差分数组得出了sum(p)=a[p]，这里求前缀和当然是求a[0]+a[1]+…+a[p]了~剩下的全是算数
a[0]+a[1]+a[2]+a[3]+…+a[p]=0+sum(1)+sum(2)+sum(3)+…+a[p]=(b[1])+(b[1]+b[2])+(b[1]+b[2]+b[3])+…+(b[1]+…+b[p])
b[1]在sum(1..p)中都出现，共p次，b[2]在sum(2..p)出现(p-1)次，类推可得
原式=p*b[1]+(p-1)*b[2]+(p-2)*b[3]+…+1*b[p]
本来想把每一项当成一个整体用BIT搞，但发现对于不同的p值，每项也会跟着变，显然没办法……
这里看到前面系数和b[]的下标和都是(p+1)，考虑逆用倒序相加大法：
原式=(p+1)*(b[1]+b[2]+b[3]+…+b[p])-(1*b[1]+2*b[2]+3*b[3]+…+p*b[p])
前面括号里是直接对b[i]求的前缀和，后面括号是对i*b[i]求前缀和——系数和下标一致的项出来了！
好，这样我们可以搞两个BIT，一个是维护b[i]的前缀和，一个维护i*b[i]的前缀和，维护方法同上
为了减少依赖所以这里仍然套了原始BIT，套BIT_ex会更好写，上代码：
struct BIT_im { BIT t1; BIT t2; void init(int s) {t1.init(s); t2.init(s);} void chage(_int l, _int r, _int k) { t1.change(l,k); t1.change(r+1,-k); t2.change(l,l*k); t2.change(r+1,-(r+1)*k); } _int sum(_int p) {return (p+1)*t1.sum(p)-t2.sum(p);}};
3.二维（多维）树状数组：
一维是前缀和，sum(p)=sum{a[i],i<=p} 求区间和
二维的话，sum(x,y)=sum{a[i][j],i<=x&&j<=y} 求矩形和
多维类似，只讨论二维
静态维护很简单：
for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
这样如果求(x1,y1)-(x2,y2)构成的矩形和，ans=s[x2][y2]-s[x1-1][y2]-s[x2,y1-1]+s[x1-1][y1-1]
那么动态维护呢？首先对(a[i])[]这个数组可以用BIT来维护一个前缀和，再维护维护(a[i])[]前缀和BIT的前缀和……好绕
总之呢，可以先用一组BIT可以维护多条平行线上的和，再用一个和它们正交的BIT把它们挂进去维护，此时原来那组BIT的意义其实已经变了……
这个思路比较像下面这段代码（鸣谢mlzmlz95）：
for(i=1;i<=n;++i) for(j=1;j<=m;++j) sum[i][j]=sum[i][j-1]+a[i][j];for(j=1;j<=m;++j) for(i=1;i<=n;++i) sum[i][j]=sum[i][j]+sum[i-1][j];
那么上代码：
struct BIT_2D { BIT c[N]; int n; void init(int s1,int s2) {n=s1; while (s1) c[s1--].init(s2);} void change(int x,int y,int k) {for (; x<=n; x+=x&-x) c[x].change(y,k);} int sum(int x,int y) {int s=0; for (; x; x-=x&-x) s+=c[x].sum(y); return s;}};
这个实现中，我们通过外层BIT来确定里层BIT的更新，初始化要把它们循环一遍设定好尺寸
至于3D，那就再挂个2D吧，不过求一个长方体和的公式有点复杂>_<
那么想搞多维难道就要把前面所有维的写出来吗……太麻烦了，我们直接手工inline一下，再稍作修改：
struct BIT_2D_in { int c[N][M],n,m; void init(int s1,int s2) {n=s1; m=s2; memset(c,0,sizeof(c));} void change(int xx,int yy,int k) { for (int x=xx; x<=n; x+=x&-x) for (int y=yy; y<=m; y+=y&-y) c[x][y]+=k; } int sum(int xx,int yy) { int s=0; for (int x=xx; x; x-=x&-x) for (int y=yy; y; y-=y&-y) s+=c[x][y]; return s; }};
这个实现中，我们可以看出来这两重循环直接控制好了下标，那么多维直接加几重循环就完事了，xx,yy当参数名可以在后面循环写x,y，我懒……
没了……其实全文可能没啥新鲜的
下期预告：邪道（写萎）的BIT
转载请注明原文链接：树状数组整理（2.区间修改、二维）
