點選打開檢視論文 這篇論文詳細介紹了樹狀數組和二進制思想的巧妙,讀後很受啟發。
在下面整理了區間更新,單點查詢的模闆,分别對應于二維、三維樹狀數組。
1.二維樹狀數組poj 2155 Matrix
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=1010;
int n;
int c[maxn][maxn];
int lowbit(int k)
{
return k&(-k);
}
void update(int x,int y,int v)
{
while(x<=n)
{
int j=y;
while(j<=n)
{
c[x][j]+=v;
j+=lowbit(j);
}
x+=lowbit(x);
}
}
int getsum(int x,int y)
{
int cnt=0;
while(x>0)
{
int j=y;
while(j>0)
{
cnt+=c[x][j];
j-=lowbit(j);
}
x-=lowbit(x);
}
return cnt;
}
int main()
{
int t,q;
int x,y,xx,yy;
scanf("%d",&t);
while(t--)
{
memset(c,0,sizeof(c));
scanf("%d%d",&n,&q);
while(q--)
{
char c;
cin>>c;
if(c=='C')
{
scanf("%d%d%d%d",&x,&y,&xx,&yy); x++;y++;xx++;yy++;
update(x,y,1);
update(x,yy+1,1);
update(xx+1,y,1);
update(xx+1,yy+1,1);
}
else if(c=='Q')
{
scanf("%d%d",&x,&y); x++;y++;
printf("%d\n",getsum(x,y)%2);
}
}
if(t) printf("\n");
}
return 0;
}
2.三維樹狀數組 hdu 3584 Cube
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=110;
int n;
int c[maxn][maxn][maxn];
int lowbit(int k)
{return k&(-k);}
void update(int x,int y,int z,int v)
{
int i,j,k;
for(i=x;i<maxn;i+=lowbit(i))
for(j=y;j<maxn;j+=lowbit(j))
for(k=z;k<maxn;k+=lowbit(k))
{
c[i][j][k]+=v;
}
}
int getsum(int x,int y,int z)
{
int i,j,k;
int cnt=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))
cnt+=c[i][j][k];
return cnt;
}
int main()
{
int m,f;
int x,y,z,xx,yy,zz;
while(~scanf("%d%d",&n,&m))
{
memset(c,0,sizeof(c));
while(m--)
{
scanf("%d",&f);
if(f==1)
{
scanf("%d%d%d%d%d%d",&x,&y,&z,&xx,&yy,&zz); x++;y++;z++; xx++;yy++;zz++;
update(x,y,z,1);
update(x,yy+1,zz+1,1);
update(xx+1,y,zz+1,1);
update(xx+1,yy+1,z,1);
update(x,y,zz+1,1);
update(x,yy+1,z,1);
update(xx+1,y,z,1);
update(xx+1,yy+1,zz+1,1);
}
else if(f==0)
{
scanf("%d%d%d",&x,&y,&z); x++;y++;z++;
printf("%d\n",getsum(x,y,z)%2);
}
}
}
return 0;
}