title: Fastest way to find sum of any rectangle in matrix
body: <p>I have a m x n matrix and want to be able to calculate sums of arbitrary rectangular submatrices. This will happen several times for the given matrix. What data structure should I use?</p>
  
  <p>For example I want to find sum of rectangle in matrix </p>
  
  <pre><code>1   2   3   4
  5   6   7   8
  9   10  11  12
  13  14  15  16
  </code></pre>
  
  <p>Sum is 68.</p>
  
  <p>What I'll do is accumulating  it row by row:</p>
  
  <pre><code>1   2   3   4
  6   8   10  12
  15  18  21  24
  28  32  36  40
  </code></pre>
  
  <p>And then, if I want to find sum of the matrix I just accumulate  <strong>28,32,36,40 = 136</strong>. Only four operation instead of 15.
  If I want to find sum of second and third row, I just accumulate <strong>15,18,21,24</strong> and subtract <strong>1, 2, 3, 4.</strong> = 6+8+10+12+15+18+21+24 = <strong>68</strong>.
  But in this case I can use another matrix, accumulating this one by columns:</p>
  
  <pre><code>1   3   6   10
  5   11  18  26
  9   19  30  42
  13  27  42  58
  </code></pre>
  
  <p>and in this case I just sum <strong>26</strong> and <strong>42</strong> = <strong>68</strong>. Only 2 operation instead of 8.  For wider sub-matrix is is efficient to use second method and matrix, for higher - first one. Can I somehow split merge this to methods to one matrix?</p>
  
  <p>So I just sum to corner and subtract another two?</p>