我有一个三维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
这是二维案例:
最佳答案
公式总共涉及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).
关于algorithm - 3d 芬威克树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11713562/