title: 3D variant for summed area table (SAT)
body: <p>As per Wikipedia:</p>
  
  <p>A <a href="http://en.wikipedia.org/wiki/Summed_area_table" rel="nofollow">summed area table</a> is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid.</p>
  
  <p>For a 2D space a summed area table can be generated by iterating <code>x,y</code> over the desired range,  </p>
  
  <pre><code>I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)
  </code></pre>
  
  <p>And the <code>query</code> function for a rectangle corners <code>A(top-left)</code>, <code>B(top-right)</code>, <code>C(bottom-right)</code>, <code>D</code> can be given by:-</p>
  
  <pre><code>I(C) + I(A) - I(B) - I(D)
  </code></pre>
  
  <p>I want to convert the above to 3D. Also please tell if any other method/data structure available for calculating partial sums in 3D space.</p>