二维树状数组
本文最后更新于:2017年9月14日 晚上
BIT是最容易扩展到高维的数据结构了,对于一维(单点修改+区间查询
),我们是这样搞得……
#define lowbit(x) ((x)&(-(x)))
void update(int pos,int val)
{
for(int i=pos;i<=n;i+=lowbit(i)) sum[i]+=val;
}
int query(int pos)
{
int ret=0;
for(int i=pos;i;i-=lowbit(i)) ret+=sum[i];
return ret;
}
int getsum(int l,int r)
{
return query(r)-query(l-1);
}
单点修改+区间查询
至于二维,容斥一下。
#define lowbit(x) ((x)&(-(x)))
void update(int x,int y,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
{
for(int j=y;j<=n;j+=lowbit(j))
{
f[i][j]+=val;
}
}
}
int query(int x,int y)
{
int ret=0;
for(int i=x;i;i-=lowbit(i))
{
for(int j=y;j;j-=lowbit(j))
{
ret+=f[i][j];
}
}
return ret;
}
int getsum(int x1,int y1,int x2,int y2)
{
return query(x2,y2)+query(x2,y1-1)+query(x1-1,y2)-query(x1-1,y1-1);
}
区间修改+单点查询
和一维一样差分。
每次修改红色区域,用类似前缀和的思想。
#define lowbit(x) ((x)&(-(x)))
void update(int x,int y,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
{
for(int j=y;j<=n;j+=lowbit(j))
{
f[i][j]+=val;
}
}
}
int query(int x,int y)
{
int ret=0;
for(int i=x;i;i-=lowbit(i))
{
for(int j=y;j;j-=lowbit(j))
{
ret+=f[i][j];
}
}
return ret%2;
}
void UP(int x1,int y1,int x2,int y2)
{
update(x1,y1,1);
update(x1,y2+1,-1);
update(x2+1,y1,-1);
update(x2+1,y2+1,1);
}
本博客所有文章除特別声明外,均采用
CC BY 4.0
许可协议。转载请注明来源
SpaceSkyNet
!