一维树状数组和二维树状数组和三维树状数组的区间更新单点求值

87 阅读 0 评论 58 点赞

我是靠谱客的博主酷炫板凳，最近开发中收集的这篇文章主要介绍一维树状数组和二维树状数组和三维树状数组的区间更新单点求值，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

树状数组作为一种十分精巧的数据结构,代码十分好写,简直逆天,最近碰到的同样逆天的有Floyd算法。但是树状数组有一个十分蛋疼的地方，只有单点更新，区间求和。因此常见的变形变有了，区间更新，单点求值。分为1维和多维。

/*
一维的 典型应用 color the ball.
我们想新构建一个数组
使得a[n]=d[1]+d[2]+..d[n];
则问题可以转化
即对d数组的求和相当于a数组单点的值
那么思考如何构建这么一个数组
对！
d[n]=a[n]-a[n-1] 且n>2
d[1]=a[1].
最后一个问题
a的区间如何更新?
由于d[n]=a[n]-a[n-1]，不位于端点的点值不会改变
假设更新的区间为[a,b],只需要a点+val,b+1点-val.
那么这个问题就可以很直观的解决了
附上一维的代码
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int c[110000];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
while(x<=n)
{
c[x]+=val;
x+=lowbit(x);
}
}
int query(int x)
{
int sum=0;
while(x>0)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
int i,a,b;
while(scanf("%d",&n)!=EOF &&n)
{
memset(c,0,sizeof(c));
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
update(a,1);
update(b+1,-1);
}
for(i=1;i<=n;i++)
{
printf("%d",getsum(i));
if(i<n)
printf(" ");
else printf("n");
}
}
return 0;
}

/*
同样二维的,a[][]的区间更新(即矩形的更新)，单点求值，我们希望构建一个数组
a[i][j]=d[1][1]+...d[i-1][j]+d[i][j-1]+d[i][j];
构建的方法是
d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1];
这样的话查询求和即求d[1][1]~d[i][j]的求和
对矩形的更新:当要给矩形a[x1][y1],a[x2][y2]加上val的时候，
只需要在数组d上对d[x1][y1], d[x2+1][y2+1]进行一般树状数组的更新val的操作
同时对d[x1][y2+1], d[x2+1][y1]进行一般树状数组的更新-val的操作即可。
典型应用是POJ2155
*/
#include
#include
#include
int m;
int c[1010][1010];
int lowbit(int i)
{
return i&(-i);
}
int query(int x,int y)
{
int sum=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
sum+=c[i][j];
return sum;
}
void update(int x,int y,int val)
{
for(int i=x;i<=m;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
c[i][j]+=val;
}
int main()
{
int n,i,x1,y2,x2,y1,x,y,t;
char ch;
scanf("%d",&t);
while(t--)
{
memset(c,0,sizeof(c));
int ans=0;
scanf("%d%d",&m,&n);
for(i=0;i<n;i++)
{
getchar();
scanf("%c",&ch);
if(ch=='C')
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x2++;
y2++;
update(x1,y1,1);
update(x1,y2,-1);
update(x2,y1,-1);
update(x2,y2,1);
}
else if(ch=='Q')
{
scanf("%d%d",&x,&y);
printf("%dn",(1&query(x,y)));
}
}
printf("n");
}
return 0;
}


/*
三维树状数组
典型应用 hdu 3584
*/
#include
#include
#include
using namespace std;
#define maxn 101
int c[maxn][maxn][maxn];
int m;
int lowbit(int x)
{
return x&(-x);
}
int query(int x,int y,int z)
{
int i,j,k;
int sum=0;
for(i=x;i>0;i-=lowbit(i))
for(j=y;j>0;j-=lowbit(j))
for(k=z;k>0;k-=lowbit((k)))
sum+=c[i][j][k];
return sum;
}
void update(int x,int y,int z,int val)
{
int i,j,k;
for(i=x;i<=m;i+=lowbit(i))
for(j=y;j<=m;j+=lowbit(j))
for(k=z;k<=m;k+=lowbit(k))
c[i][j][k]+=val;
}
int main()
{
int n;
while(scanf("%d%d",&m,&n)!=EOF)
{
int tt,i;
memset(c,0,sizeof(c));
int x,x1,x2,y,y1,y2,z,z1,z2;
for(i=0;i<n;i++)
{
scanf("%d",&tt);
if(tt==1)
{
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
x2++;
y2++;
z2++;
update(x2,y2,z2,1);
//x2,y2,z2
update(x1,y2,z2,1);
//x1,y2,z2
update(x2,y1,z2,1);
//x2,y1,z2
update(x2,y2,z1,1);
//x2,y2,z1
update(x1,y1,z2,1);
//x1,y1,z2
update(x2,y1,z1,1);
//x2,y1,z1
update(x1,y2,z1,1);
//x1,y2,z1
update(x1,y1,z1,1);
//x1,y1,z1
}
else
{
scanf("%d%d%d",&x,&y,&z);
printf("%dn",query(x,y,z)&1);
}
}
}
return 0;
}