algorithm - 3 d のフェンウィック ツリー

Question

私は 3 次元のフェンウィック ツリーデータ構造を持っています。(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).