本文主要是介绍HDU3584 Cube【树状数组】【三维】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3584
题目大意：
给定一个N*N*N多维数据集A，其元素是0或是1。A[i，j，k]表示集合中第 i 行，第 j 列与第 k 层的值。
首先由A[i，j，k] = 0(1 <= i，j，k <= N)。
给定两个操作：
1：改变A[i，j，k]为！A[i，j，k]。
2：查询A[i，j，k]的值。
思路：
三维树状数组区间更新、单点查询。更新区间(a，b)时，在 a 和 b+1 处都加1，前边表示增加1，后边是
抵消加1操作，最后询问时，用Query(x) % 2 即为单点的值(0或1)。三维区间更新，要注意区间的合并会
重复，所以要利用容斥原理，更新区间(x1，y1，z1)~(x2，y2，z2)时，需要利用容斥原理。更新如下：
Update(x1,y1,z1); Update(x1,y1,z2+1); Update(x1,y2+1,z1); Update(x1,y2+1,z2+1);
Update(x2+1,y1,z1); Update(x2+1,y1,z2+1); Update(x2+1,y2+1,z1); Update(x2+1,y2+1,z2+1);
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 110;int Tree[MAXN][MAXN][MAXN],N,M;int Lowbit(int i)
{return i & (-i);
}void Update(int x,int y,int z)
{for(int i = x; i <= N; i += Lowbit(i))for(int j = y; j <= N; j += Lowbit(j))for(int k = z; k <= N; k += Lowbit(k))Tree[i][j][k]++;
}int Query(int x,int y,int z)
{int sum = 0;for(int i = x; i > 0; i -= Lowbit(i))for(int j = y; j > 0; j -= Lowbit(j))for(int k = z; k > 0; k -= Lowbit(k))sum += Tree[i][j][k];return sum;
}int main()
{while(cin >> N >> M){memset(Tree,0,sizeof(Tree));int op,x1,y1,z1,x2,y2,z2;while(M--){cin >> op;if(op == 0){cin >> x1 >> y1 >> z1;cout << Query(x1,y1,z1) % 2 << endl;}else{cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;Update(x1,y1,z1);Update(x1,y1,z2+1);Update(x1,y2+1,z1);Update(x1,y2+1,z2+1);Update(x2+1,y1,z1);Update(x2+1,y1,z2+1);Update(x2+1,y2+1,z1);Update(x2+1,y2+1,z2+1);}}}return 0;
}
这篇关于HDU3584 Cube【树状数组】【三维】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
