array with o(1)

Question

I am trying to find the sum of a random subset in a 2D array in o(1) complexity, size up to array[1000][1000] but lets take [4][4] as a basic example:

array[4][4] = {0, 1, 2 ,3
              4, 5, 6, 7
              8, 9, 10, 11
              12, 13, 14, 15}

I have seen some implementations for 1 dimensional arrays where you store the running sum and then just subtract.

That makes sense but lets say I want the sum of array[2][2] to array[3][3] in o(1). So it'd be 10 + 11 + 14 + 15.

But how can this be done in o(1)? o(n) is easy.

Is it something to do with hash tables or a more complicated pre-processed array?

edit>>>

Just some additioanl notes for anyone who comes back to this question:

1. The specific wording that is useful when googling this seems to be 'summed-area table' or 'integral image' or 'Viola–Jones object detection framework'
2. Useful references include https://computersciencesource.wordpress.com/2010/09/03/computer-vision-the-integral-image/ and https://en.wikipedia.org/wiki/Viola%E2%80%93Jones_object_detection_framework and https://en.wikipedia.org/wiki/Summed-area_table

Answer 1

For each element [i][j], precompute the sum of all elements in the rectangle spanning from array[0][0] to array[i][j]; denote this value sums[i][j]. Then, to compute the sum of a rectangular subset i1 <= i <= i2 and j1 <= j <= j2, compute:

sums[i2][j2] 
- (i1 == 0 ? 0 : sums[i1 - 1][j2]) 
- (j1 == 0 ? 0 : sums[i2][j1 - 1]) 
+ ((i1 == 0 || j1 == 0) ? 0 : sums[i1-1][j1-1])

The bounds checks are used to avoid an illegal access outside of array bounds when the region of interest includes i==0 or j==0.

As a rough geometric argument, see the below figure. To get the sum in the black rectangle, get the orange rectangle, subtract the red and green ones, and add back the purple one (since it got double-subtracted).