三维前缀和 C++
三维前缀和是指在三维数组中,对于每个位置上的元素,计算该位置及其左上角所有元素的和。
如果我们用一个三维数组prefixSum[x][y][z]来表示三维前缀和,其中x、y和z分别表示三维数组的三个维度上的索引
三维区间求和,考验空间想象能力。
前缀和表达式:
s[i][j][k]=s[i][j][k−1]+s[i][j−1][k]+s[i−1][j][k]−s[i−1][j−1][k]−s[i−1][j][k−1]−s[i][j−1][k−1]+s[i−1][j−1][k−1]+f[i][j][k]
(x1,x2,y1,y2,z1,z2)的区间的和为:
s[x2][y2][z2]−s[x1−1][y2][z2]−s[x2][y1−1][z2]−s[x2][y2][z1−1] + s[x2][y1−1][z1−1] + s[x1−1][y2][z1−1] + s[x1−1][y1−1][z2]−s[x1−1][y1−1][z1−1]