首页 / MYSQL / 树状数组整理（2.区间修改、二维）
树状数组整理（2.区间修改、二维）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了树状数组整理（2.区间修改、二维），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3924字，纯文字阅读大概需要6分钟。
内容图文
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]，这样成段修改时：
对i
但b[l]'=(a[l]+k)-a[l-1]=b[l]+k；b[r+1]'=a[r+1]-(a[r]+k)=b[r+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.区间修改、二维）全部内容，希望文章能够帮你解决树状数组整理（2.区间修改、二维）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。