This content is archived!For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.
2D Prefix Sum Array
The underlying structure is a simple 2D array of size
[C + 1][R + 1], where
R are the respective sizes of the original array.
Say we have this grid, full of 1s:
The prefix sum array would look like:
psa[c][r] contains the sum of the region [(0,0),(c−1,r−1)].
psa has a value of
Say we only wanted the sum of the region [(1,2),(2,2)]. We would have an extra region, highlighted in pink.
We must subtract the region. However, when we use two rectangles to subtract the region, we have subtracted another rectangular region an additional time. Thus, we must add it back.
Our final expression for the sum is:
ps - ps - ps + ps = 9 - 3 - 6 + 2 = 2
A generalized formula for the sum of a rectangle [(c1,r1),(c2,r2)] is
ps[c2 + 1][r2 + 1] - ps[c1][r2 + 1] - ps[c2 + 1][r1] + ps[c1][r1]
Construction is done iteratively from top to bottom, left to right. At each point, the respective rectangular region excluding the right-bottommost square is summed, and added to the right-bottommost square from the original array. Green represents the already calculated sums. Gold is the current square.
Similar to summing up a rectangular region, there will be a repeated region which will be subtracted.
Construction of a 2D prefix sum array
psa from 2D array
a of size
Query sum of rectangular region with left-top corner at (c1,r1) and bottom-right corner at (c2,r2).
Alternatively, if the rectangular region is represented by [(c,r),(c+w+1,r+h+1)]. (c,r) is the starting square, and the rectangle is w squares wide and h squares high.
Sum Query: O(1)
The 2D prefix sum array is slightly more complicated than the 1D version, but still very fast. How about 3D prefix sum arrays?
DMOPC ‘15 Contest 1 P5 - Lelei and Dragon Scales
MEC ‘16 P6 - Instruments of the Ghostwriters