hdu 3584 三维树状数组

  1. /****************************************************************************************************
  2. 题意：在一个三维长方体里把0元素改成1或者把1改成0或者询问某个位置是0还是1.
  3. 分析:
  4. 非树状数组莫属，其他数据结构都太帅了，用不着。
  5. 先说说一维上的树状数组，什么问题都得成最简单的开始，理解后才能推广到多维或复杂的。
  6. 把对某个方体的修改操作看做是对某个方体的操作数+1，那一个位置操作数的奇偶性决定了它的值。
  7. 树状数组1位置是管1的，2位置是管1到2的,3是管3的，4是管1到4的......所以对一个区间操作，这个区间首先按树状数组的分区规则，会被分成若干个不相交的区间，在树状数组里对应的就是若干不相交的小树。
  8. 比如对1到3操作，会分成分别对[1,2],[3,3]两段的操作；对2到4的操作，可以分成[2,2],[3,3],[4,4]，但是对这种情况，按这种方式去修改树状数组是麻烦的，可以转化成分别对[1,4]操作，再对[1,1]操作，这样[1,1]被修改了两次，所以相当于没修改过(配合这题的奇偶性)，也可处理成对[1,4]的操作数+1，再对[1,1]的操作数-1。
  9. 知道每段的信息保存操作次数，可以通过叠加就知道每个位置的操作数。
  10. 比如对1到3操作了一次，c[2] = 1(对应[1,2]的区间)，c[3] = 1(对应[3,3]区间)；再对1操作，则c[1] = 1（对应[1,1]区间）。则1的操作数是c[1] + c[2]。
  11. 到此还不理解的，建议最好看看树状数组的详细结构，然后画一画就应该清楚多了，表达上的不便请原谅，这个算是比较水的，不过对树状数组的理解是有点用处的，还有就是在树状数组上对方块的切割，例如对对2到4的操作需要处理成[1,4]操作，再对[1,1]操作 ，将这个操作推广到3维。
  12. 一维的是区间管区间，二维是方块管理方块，三维是方体管理方体，本质跟一维一样。
  13. *****************************************************************************************************/
  15. #include <stdio.h>
  16. #include <string.h>
  19. int cube[110][110][110];
  20. int n;
  21. int lowbit(int x)
  22. {
  23. 	return x&-x;
  24. }
  26. void update(int x, int y, int z)
  27. {
  28. 	for(int i=x; i<=n; i+=lowbit(i) )
  29. 		for(int j=y; j<=n; j+=lowbit(j) )
  30. 			for(int k=z; k<=n; k+=lowbit(k) )
  31. 				cube[i][j][k]++;
  32. }
  34. int sum(int x, int y, int z)
  35. {
  36. 	int all =0;
  37. 	for(int i=x; i>0; i-=lowbit(i) )
  38. 		for(int j=y; j>0; j-=lowbit(j) )
  39. 			for(int k=z; k>0; k-=lowbit(k) )
  40. 				all += cube[i][j][k];
  41. 	return all;
  42. }
  44. int main()
  45. {
  46. 	//freopen("read.txt", "r", stdin);
  48. 	int m;
  49. 	while(~scanf("%d%d", &n, &m))
  50. 	{
  51. 		memset(cube, 0, sizeof(cube) );
  52. 		int sign;
  53. 		while(m--)
  54. 		{
  55. 			scanf("%d", &sign);
  56. 			if(sign)
  57. 			{
  58. 				int x1, y1, z1, x2, y2, z2;
  59. 				scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
  60. 				update(x2+1, y2+1, z2+1);				//因为为了防止计算时下标变为1， 所以更新时都增加1。
  61. 				update(x2+1, y1, z2+1);
  62. 				update(x1, y2+1, z2+1);
  63. 				update(x1, y1, z2+1);
  64. 				//--------
  65. 				update(x2+1, y2+1, z1);
  66. 				update(x2+1, y1, z1);
  67. 				update(x1, y2+1, z1);
  68. 				update(x1, y1, z1);
  69. 			}
  71. 			else
  72. 			{
  73. 				int x, y, z;
  74. 				scanf("%d%d%d",&x, &y, &z);
  75. 				printf("%d
", sum(x, y, z)%2);				//重复操作次数的余项
  76. 			}
  77. 		}
  78. 	}
  79. 	return 0;
  80. }
  83. /*
  84. 很容易想到三维线段树，但操作过于复杂。果断用树状数组，由一维开始：
  86. 每次修改的时候，给定一个格子修改的范围（x,y）。把这个范围变成两个点，一个为更改的初始节点x，另一个为终止结点y+1（不是y），然后这两个节点加1,向根节点上溯，节点+1。
  88.                      x                           y+1
  90. 0	0	1	0	0	1	0	0	0	0
  91. insert x,y+1
  93. 每次询问x的时候只需计算sum=sigma(a[i],0<i<=x),即第x个数被修改了sum次，状态为sum%2。
  95. 对于二维的情况，加上四个格子即可(x1,y1), (x1,y2+1), (x2+1,y1), (x2+1,y2+1)，每次修改的时候这四个格子加1。
  97. (x1,y1)	0	0	(x2+1,y1)	0
  98. 0	0	0	0	0
  99. 0	0	0	0	0
  100. (x1,y2+1)	0	0	(x2+1,y2+1)	0
  101. 0	0	0	0	0
  102.  
  104. insert (x1,y1)   (x1,y2+1)   (x2+1,y1)   (x2+1,y2+1)
  106. 查询（x，y）时输出sum=sigma(a[i][j],0<i<=x&&0<j<=y)即可。
  108. 三维的时候加8个点，n维加2^n个点。
  109. */





附件列表

    【推广】 免费学中医，健康全家人
    原文地址：https://www.cnblogs.com/sober-reflection/p/2021d100acb1842f65a86add16640082.html