AlgoScope

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).

Range queries, algorithm, intermediate
Prefix cell 1, 1 is 3.012340123000000300
Prefix cell 1, 1 is 3.012340123000000300

Matrix: 2D prefix sum

Decision, step 2 of 14

p[1][1]: own value 3, plus above 0, plus left 0, minus the diagonal 0 that both of those already include: 3.

How matrix works

Cost

Best
O(r * c)
Average
O(r * c)
Worst
O(r * c)
Space
O(r * c)

O(1) per query after building.

Leads to

Topics that need this one first.

Taught by the same lesson

Matrix covers these too, in the same run.