Sign in to watch this lesson
Algorithms - Arrays · 4:36
2D Prefix Sums and Submatrix Queries
Prefix sums move from a staircase to a grid: a table of corner sums, built in one pass with one overlap correction per cell, answers the sum of any rectangle with four lookups. We derive the four-corner formula from overlapping rectangles, time it against a plain loop on a Mac, and use it for sliding k-by-k windows and for the maximum-sum submatrix via row pairs and Kadane.
You will learn
- Build a 2D prefix table P with a zero border using P[i][j] = a + up + left - overlap
- Answer any rectangle sum in O(1) with the four-corner formula and explain its sign pattern
- Score every k x k window of a grid in O(nm) total
- Find a maximum-sum submatrix in O(n^2 m) by fixing row pairs and running Kadane on column totals