求和面积表 (SAT) 的 3D 变体

根据维基百科：

A 面积求和表 http://en.wikipedia.org/wiki/Summed_area_table是一种数据结构和算法，用于快速有效地生成网格矩形子集中的值之和。

对于二维空间，可以通过迭代生成求和面积表x,y超过所需的范围，

I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)

And the query矩形角的函数A(top-left), B(top-right), C(bottom-right), D可以通过以下方式给出：-

I(C) + I(A) - I(B) - I(D)

我想将上面的内容转换为 3D。另请告知是否有任何其他方法/数据结构可用于计算 3D 空间中的部分和。

我不确定，但可以想到类似以下的内容。 （我还没有浏览维基百科代码）

对于每个坐标 (x,y,z)，求从 (0,0,0) 到该元素的所有元素的总和。
将其称为 S(0,0,0 到 x,y,z) 或 S0(x,y,z)。
这可以通过遍历 3D 矩阵一次来轻松构建。

S0( x,y,z ) =  value[x,y,z] + S0(x-1,y-1,z-1) + 
               S0( x,y,z-1 ) + S0( x, y-1, z ) + S0( x-1, y, z ) 
               - S0( x-1, y-1, z ) - S0( x, y-1, z-1 ) - S0( x-1, y, z-1 )

（基本上元素值 + S0(x-1,y-1,z-1) + 3 个面 (xy,yz,zx) ）

现在，对于每个查询 (x1,y1,z1) 到 (x2,y2,z2)，首先转换坐标，使 x1,y1,z1 是最接近原点的长方体的角，x2,y2,z2 是最接近原点的角距离原点最远。

S( (x1,y1,z1) to (x2,y2,z2) ) = S0( x2,y2,z2 ) - S0( x2, y2, z1 ) 
                                - S0( x2, y1, z2 ) - S0( x1, y2, z2 )
                                + S0( x1, y1, z2 ) + S0( x1, y2, z1 ) + S0( x2, y1, z1 )
                                - S0( x1, y1, z1 )

（有待更正）