title: 3d Fenwick tree
body: <p>I have a three-dimensional <a href="http://en.wikipedia.org/wiki/Fenwick_tree" rel="noreferrer">fenwick tree</a> data structure.
  I need to calculate sum on some segment from <code>(x0, y0, z0)</code> to <code>(x, y, z)</code></p>
  
  <p>What is the formula for inclusion-exclusion?
  For instance, for 2D variant it is</p>
  
  <pre><code>s = sum(x, y) - sum(x, y0 - 1) - sum(x0 - 1, y) + sum(x0 - 1, y0 - 1)
  </code></pre>
  
  <p>Thanks in advance</p>
  
  <p><a href="http://www.comp.nus.edu.sg/~stevenha/ft.pdf" rel="noreferrer">http://www.comp.nus.edu.sg/~stevenha/ft.pdf</a></p>
  
  <p>Here is 2D case: 
  <img src="https://i.stack.imgur.com/4a7D2.jpg" alt="enter image description here"></p>