CODEWITHSUNDEEP
algorithm3dtreefenwick-tree
Denys Astanin
Denys Astanin

Reputation: 71

3d Fenwick tree

I have a three-dimensional fenwick tree data structure. I need to calculate sum on some segment from (x0, y0, z0) to (x, y, z)

What is the formula for inclusion-exclusion? For instance, for 2D variant it is

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

Thanks in advance

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

Here is 2D case: enter image description here

Upvotes: 7

Views: 3077

Answers (1)

TLE
TLE

Reputation: 705

formula involves total 8 computations

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

Time complexity of code is 8 (logn)^3

How can you visualize.

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

Upvotes: 6

Related Questions