二维树状数组

二维的区间修改+单点查询可以用类似二维差分的方法来解决

二维前缀和：

我们可以令差分数组表示与 的差。

代码如下：

void add(int x,int y,int v)
{
while(x<=n)
{
int ty=y;
while(ty<=n)
tree[x][ty]+=v,ty+=lowbit(ty);
x+=lowbit(x);
}
}
void real_add(int x1,int y1,int x2,int y2,int v)
{
add(x1,y1,v);
add(x1,y2+1,-v);
add(x2+1,y1,-v);
add(x2+1,y2+1,v);
}
int ask(int x, int y)
{
int res=0;
while(x)
{
int ty=y;
while(ty)
res+=tree[x][ty],ty-=lowbit(ty);
x-=lowbit(x);
}
return res;
}

最后思考如何区间修改+区间查询：

同样首先思考一维树状数组如何进行区间修改+区间查询

基于上文的差分思路，我们知道位置p的前缀和为 

在等式最右侧的式子中，被用了p次，被用了次……那么我们可以得出：

位置p的前缀和为 

于是我们可以维护两个数组的前缀和：
一个数组是 
另一个数组是 

位置p的前缀和即：数组中p的前缀和 - sum2数组中p的前缀和。

区间[l, r]的和即：位置r的前缀和 - 位置l的前缀和。

代码如下：

void add(int x,int v)
{
int p=x;
while(x<=n)
{
sum1[x]+=v;
sum2[x]+=v*p;
x+=lowbit(x);
}
}
void real_add(int l,int r,int v)
{
add(l,v),
add(r+1,-v);
}
int ask(int x)
{
int res=0;
int p=x;
while(x)
{
res+=(p+1)*sum1[x]-sum2[x];
x-=lowbit(x);
}
return res;
}
int real_ask(int l,int r)
{
return ask(r)-ask(l-1);
}

同理，二维的区间修改+区间查询也可以用类似的思路来解决

类比之前一维数组的区间修改区间查询，下面这个式子表示的是点(x, y)的二维前缀和：

首先，类比一维数组，统计一下每个出现过多少次。出现了次，出现了次……出现了 次。

那么这个式子就可以写成：

把这个式子展开，就得到：

那么我们要开四个树状数组，分别维护：

,,,

这样就可以解决上述问题了

代码如下：
 

void add(int x,int y,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
{
t1[i][j]+=v;
t2[i][j]+=v*x;
t3[i][j]+=v*y;
t4[i][j]+=v*x*y;
}
}
void real_add(int x1,int y1,int x2,int y2,int v)
{
add(x1,y1,v);
add(x1,y2+1,-v);
add(x2+1,y1,-v);
add(x2+1,y2+1,v);
}
int ask(int x, int y)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
res+=(x+1)*(y+1)*t1[i][j]-(y+1)*t2[i][j]-(x+1)*t3[i][j]+t4[i][j];
return res;
}
int real_ask(int x1,int y1,int x2,int y2)
{
return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
}

最后

以上就是乐观小懒猪为你收集整理的二维树状数组的全部内容，希望文章能够帮你解决二维树状数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。