ural 1470 UFOs [树状数组]

题意：

对（0，0，0）到（128，128，128）的三维空间进行三种操作：（1）在点（x，y，z）增加V（可能为负）；（2）查询（x1，y1，z1）到（x2，y2，z2）的数量和；（3）退出

三种操作是实时的。

思路：

可以向上一题一样采用线段树，但是需要三重线段树，编程复杂度有点高，于是简单的树状数组，查询的时候用差值。树状数组这里讲得比较清楚：click me

#include <cstdio>
#include <cstring>
#define N 130
int c[N][N][N], n;
void update(int px, int py, int pz, int val)
{
	int x=px, y=py, z=pz;
	while (x <= n)
	{
		y = py;
		while (y <= n)
		{
			z = pz;
			while (z <= n)
			{
				c[x][y][z] += val;
				z += z&(-z);
			}
			y += y&(-y);
		}
		x += x&(-x);
	}
}
int quary(int px, int py, int pz)
{
	int ret=0, x=px, y=py, z=pz;
	while (x > 0)
	{
		y = py;
		while (y > 0)
		{
			z = pz;
			while (z > 0)
			{
				ret += c[x][y][z];
				z -= z&(-z);
			}
			y -= y&(-y);
		}
		x -= x&(-x);
	}
	return ret;
}
int main()
{
	while (scanf("%d",&n) != EOF)
	{
		int tag;
		while (scanf("%d",&tag) && tag!=3)
		{
			if (tag == 1)
			{
				int x1,y1,z1,v;
				scanf("%d%d%d%d",&x1,&y1,&z1,&v);
				update(x1+1,y1+1,z1+1,v);
			}
			else if (tag == 2)
			{
				int x1,y1,z1,x2,y2,z2,v;
				scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
				v = quary(x2+1,y2+1,z2+1)
					- quary(x2+1,y2+1,z1) - quary(x2+1,y1,z2+1) - quary(x1,y2+1,z2+1)
					+ quary(x1,y1,z2+1) + quary(x1,y2+1,z1) + quary(x2+1,y1,z1)
					- quary(x1,y1,z1);
				printf("%dn", v);
			}
		}
	}
}

最后

以上就是震动芒果为你收集整理的ural 1470 UFOs [树状数组]的全部内容，希望文章能够帮你解决ural 1470 UFOs [树状数组]所遇到的程序开发问题。

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