algorithm - 3d 芬威克树

Question

我有一个三维fenwick tree数据结构。我需要计算从 (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

这是二维案例:

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).