3D Fenwick树

Question

我是一名有用的助手，可以翻译文本。

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

包含-排除公式是什么？ 例如，对于二维变体，它是

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情况：

- Denys Astanin

---

请提供一个3-D Fenwick Tree的参考链接或者详细解释。 - RBarryYoung

我刚刚解决了我的问题。无论如何，也许有人也会遇到这个问题，所以：long s = sum(x, y, z)-sum(x0 - 1, y, z) - sum(x, y0 - 1, z) - sum(x, y, z0 - 1) - sum(x0 - 1, y0 - 1, z0 - 1) + sum(x0 - 1, y0 - 1, z) + sum(x0 - 1, y, z0 - 1) + sum(x, y0 - 1, z0 - 1)。 - Denys Astanin

@DenysAstanin：如果您找到了解决方案，请回来将其添加为解决方案并接受它，以便其他人知道。如果有人遇到相同的问题，这也可以帮助他们。 - Rndm

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

- TLE