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).
Matrix: 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.
Cost
- Best
- O(r * c)
- Average
- O(r * c)
- Worst
- O(r * c)
- Space
- O(r * c)
O(1) per query after building.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Matrix covers these too, in the same run.