三维树状数组,关键是更新时,空间想象比二维复杂些。其原理都是相同的!
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN =210;
int c[MAXN][MAXN][MAXN];
inline int lowbit(int x)
{
return x & (-x);
}
void Modify(int x, int y, int z, int data)
{
for(int i = x; i < MAXN; i += lowbit( i ))
for(int j = y; j < MAXN; j += lowbit( j ))
for(int k = z; k < MAXN; k += lowbit( k ))
c[i][j][k] += data;
}
int GetSum(int x, int y, int z)
{
int sum = 0;
for(int i = x; i >= 1; i -= lowbit( i ))
for(int j = y; j >= 1; j -= lowbit( j ))
for(int k = z; k >= 1; k -= lowbit( k ))
sum += c[i][j][k];
return sum;
}
int main()
{
int t;
char s[10];
int x1, y1, z1, x2, y2, z2, k;
int x, y, z;
while(scanf("%d", &t) != EOF)
{
memset(c, 0, sizeof(c));
while(t--)
{
scanf("%s", s);
if(s[0] == 'A')
{
scanf("%d %d %d %d %d %d %d", &x1, &y1, &z1, &x2, &y2, &z2, &k);
Modify(x2+1, y2+1, z2+1, -k);
Modify(x1, y2+1, z2+1, k);
Modify(x2+1, y1, z2+1, k);
Modify(x2+1, y2+1, z1, k);
Modify(x2+1, y1, z1, -k);
Modify(x1, y2+1, z1, -k);
Modify(x1, y1, z2+1, -k);
Modify(x1, y1, z1, k);
}
else if(s[0] == 'Q')
{
scanf("%d %d %d", &x, &y, &z);
printf("%d\n", GetSum(x, y, z));
}
}
}
return 0;
}