7

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

keelar
  • 5,814
  • 7
  • 40
  • 79
Denys Astanin
  • 71
  • 1
  • 3
  • Please provide either a reference (link) or a good explanation of what a 3-D Fenwick Tree it. – RBarryYoung Jul 29 '12 at 22:36
  • 2
    I've just solved my problem. Anyway, maybe, someone will stuck with this too, so: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 Jul 29 '12 at 23:05
  • @DenysAstanin : If you find the solution to your own problem , come back and add that as a solution and accept it too so that others can know and if someone has the same issue , it can help them too. – Rndm Jul 30 '12 at 14:37

1 Answers1

6

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).
TLE
  • 705
  • 1
  • 7
  • 16