2D Prefix Sum
P[i][j] = a + P[i-1][j] + P[i][j-1] - P[i-1][j-1]; any rectangle sum in O(1).
Decision · step 2 of 14Matrix: 2D prefix sum
p[1][1]: own value 3, plus above 0, plus left 0, minus the diagonal 0 that both of those already include: 3.
What you will see
The inclusion-exclusion corners light up: plus, minus, minus, plus.
Cost
| Best | O(r * c) |
|---|---|
| Average | O(r * c) |
| Worst | O(r * c) |
| Space | O(r * c) |
O(1) per query after building.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Structure nodes announce the range they cover and their value; each step announces which nodes answer the query.
Reduced motion: Contributing nodes highlight statically; no path animation.