algorithm - 3d 芬威克树

Question

我有一个三维芬威克树数据结构。我需要计算从(x0, y0, z0)到的某个段的总和(x, y, z)

包含-排除的公式是什么？例如，对于 2D 变体，它是

s = sum(x, y) - sum(x, y0 - 1) - sum(x0 - 1, y) + sum(x0 - 1, y0 - 1)

提前致谢

http://www.comp.nus.edu.sg/~stevenha/ft.pdf

这是2D案例：

Answer 1

公式共涉及 8 次计算

value1 = sum(x,y,z)- sum(x0-1,y,z)  - sum(x,y0-1,z) + sum(x0-1,y0-1,z)

value2 = sum(x,y,z0-1) - sum(x0-1,y,z0-1) - sum(x,y0-1,z0-1)  + sum(x0-1,y0-1,z0-1)


final answer = value1 - value2

代码的时间复杂度是8 (logn)^3

你怎么能形象化。

1> assume it as a cube.

2> value 1 gives answer for upper square layer of cube, but it include sum upto 0 in z-axis. 

You only want upto z0, so you have subtract that extra part(from z0 to 0, and that is value2).