Matrix
A matrix is a flat block of memory that you address with two indices. Row-major order puts row 0 first, so (r, c) lives at r x cols + c. Once that is clear, transpose is a swap across the diagonal, a 2D prefix sum is the 1D idea with one overlap to subtract, and an adjacency matrix is a graph written as a grid of 0s and 1s. A multigraph, with parallel edges and self loops, needs the same grid to count rather than flag: cell (u, v) holds the number of edges between u and v, and a loop adds 2 to its diagonal cell so that the degree is still the row sum.
Build a 2D prefix sum. p[r][c] is the sum of every value in the rectangle from the top-left corner to (r, c), with an extra zero row and column so the corner needs no special case. Each cell adds its own value to the rectangle above and the rectangle to the left, then subtracts the overlap that both contain.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 12, with their answers.
Value 3, above 0, left 0, diagonal 0. What is p[1][1]?
Answer: 3. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 0, above 0, left 3, diagonal 0. What is p[1][2]?
Answer: 3. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 1, above 0, left 3, diagonal 0. What is p[1][3]?
Answer: 4. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 4, above 0, left 4, diagonal 0. What is p[1][4]?
Answer: 8. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 5, above 3, left 0, diagonal 0. What is p[2][1]?
Answer: 8. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 6, above 3, left 8, diagonal 3. What is p[2][2]?
Answer: 14. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 3, above 4, left 14, diagonal 3. What is p[2][3]?
Answer: 18. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 2, above 8, left 18, diagonal 4. What is p[2][4]?
Answer: 24. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 1, above 8, left 0, diagonal 0. What is p[3][1]?
Answer: 9. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 2, above 14, left 9, diagonal 8. What is p[3][2]?
Answer: 17. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 0, above 18, left 17, diagonal 14. What is p[3][3]?
Answer: 21. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
Value 1, above 24, left 21, diagonal 18. What is p[3][4]?
Answer: 28. The rectangles above and to the left overlap on the diagonal one, so it comes off once.
How it runs, step by step
Build a 2D prefix sum. p[r][c] is the sum of every value in the rectangle from the top-left corner to (r, c), with an extra zero row and column so the corner needs no special case. Each cell adds its own value to the rectangle above and the rectangle to the left, then subtracts the overlap that both contain.
Building a 2D prefix sum table with a zero row and column.
p[1][1]: own value 3, plus above 0, plus left 0, minus the diagonal 0 that both of those already include: 3.
Prefix cell 1, 1 is 3.
p[1][2]: own value 0, plus above 0, plus left 3, minus the diagonal 0 that both of those already include: 3.
Prefix cell 1, 2 is 3.
p[1][3]: own value 1, plus above 0, plus left 3, minus the diagonal 0 that both of those already include: 4.
Prefix cell 1, 3 is 4.
p[1][4]: own value 4, plus above 0, plus left 4, minus the diagonal 0 that both of those already include: 8.
Prefix cell 1, 4 is 8.
p[2][1]: own value 5, plus above 3, plus left 0, minus the diagonal 0 that both of those already include: 8.
Prefix cell 2, 1 is 8.
p[2][2]: own value 6, plus above 3, plus left 8, minus the diagonal 3 that both of those already include: 14.
Prefix cell 2, 2 is 14.
p[2][3]: own value 3, plus above 4, plus left 14, minus the diagonal 3 that both of those already include: 18.
Prefix cell 2, 3 is 18.
p[2][4]: own value 2, plus above 8, plus left 18, minus the diagonal 4 that both of those already include: 24.
Prefix cell 2, 4 is 24.
p[3][1]: own value 1, plus above 8, plus left 0, minus the diagonal 0 that both of those already include: 9.
Prefix cell 3, 1 is 9.
p[3][2]: own value 2, plus above 14, plus left 9, minus the diagonal 8 that both of those already include: 17.
Prefix cell 3, 2 is 17.
p[3][3]: own value 0, plus above 18, plus left 17, minus the diagonal 14 that both of those already include: 21.
Prefix cell 3, 3 is 21.
p[3][4]: own value 1, plus above 24, plus left 21, minus the diagonal 18 that both of those already include: 28.
Prefix cell 3, 4 is 28.
Any rectangle is now four lookups. Rows 1 to 2, columns 1 to 3 of the original: p[3][4] - p[1][4] - p[3][1] + p[1][1] = 28 - 8 - 9 + 3 = 14, and adding those cells directly gives 14. O(rows x cols) to build, O(1) per query.
The rectangle from row 1 to 2 and column 1 to 3 sums to 14 from four lookups.
Remember
- Row-major: (r, c) is flat index r x cols + c. Walk rows in the inner loop and memory is touched in order.
- 2D prefix sum: own value plus above plus left minus the diagonal, and any rectangle is four lookups.
- An adjacency matrix costs V squared cells no matter how few edges there are.
Topics covered
Where this is used
Scientific computingNumPy strides and the BLAS memory order
NumPy stores an array row-major by default and keeps a stride per axis, so .T moves no data at all: it swaps the two strides and returns a view of the same buffer. LAPACK and Fortran BLAS want column-major, and the .T of a row-major array is exactly that, so the transposed view can go straight to a solver while the original array is the one that has to be copied or passed with a transpose flag. Knowing which layout you are holding is the difference between a free transpose and a full copy of the matrix.
Computer visionIntegral images in OpenCV
cv2.integral builds a 2D prefix sum of an image, and the Haar cascade detector then reads any rectangle sum in four lookups, so one feature costs a fixed handful of reads however large its boxes are. Because the cost does not grow with the rectangle, the cascade can test thousands of candidate windows at every scale per frame. The same table came out of graphics texture filtering, under the name summed-area table, before vision borrowed it.
DatabasesParquet and columnar databases
A table is a matrix and the storage engine gets to pick the traversal order. Row-major formats keep each record contiguous, which suits fetching whole rows; Parquet and ClickHouse store column-major, so a query over 2 of 50 columns reads two dense runs instead of touching every record. The compression win follows from the same choice, because a column holds one type and its values repeat.
GraphsWhy graph libraries default to lists, not matrices
An adjacency matrix answers "is there an edge u to v" in one lookup, which is exactly what dense algorithms like Floyd-Warshall need. SciPy's csgraph and NetworkX still default to sparse or list forms, because a social graph of a million vertices with ten edges each would need a trillion cells to hold ten million edges. The matrix earns its place when the graph is small or dense, or when you want to multiply it: raising it to the power k counts the walks of length k between every pair.
Why it works this way
In Java and Kotlin a 2D array is not one flat block
Array<IntArray> is an array of references, so every row is a separate object and the rows can sit anywhere on the heap. The r x cols + c model still describes the logic, but the contiguity guarantee only holds inside a single row. When layout actually matters, allocate one IntArray(rows * cols) and do the index arithmetic yourself, which is what C, Fortran and NumPy hand you for free.
Why the inner loop should walk a row, not a column
A cache line pulls in roughly 64 bytes at once, about 16 ints. Walking a row consumes all 16; walking a column uses one and throws away the rest, then fetches a fresh line on every step. The operation count is identical either way, so a column-order traversal of a large matrix can run several times slower for reasons the code does not show. Reordering the loops of a matrix multiply from i-j-k to i-k-j is the same fix.
Why transpose starts at c = r + 1, and why it needs a square
Starting at c = 0 visits every pair twice and swaps it straight back, so the loop runs and the matrix is unchanged. Starting one past the diagonal touches each pair once, and the diagonal never moves because (r, r) would swap with itself. The trick also depends on rows == cols: a 3 x 5 matrix transposes to 5 x 3, so the shape itself changes and the index map stops being a set of two-element swaps. For rectangular input you write into a new matrix or follow the permutation cycles of the index map, which is a much harder job.
Why the 2D prefix sum subtracts the diagonal term
The block above and the block to the left both already cover the region up and to the left of the current cell, so adding the two counts that overlap twice; subtracting p[r-1][c-1] once removes the extra copy. The extra zero row and column exist so that r-1 and c-1 are always in range and no boundary check is needed. The price is an off-by-one in the query: the rectangle from (r1, c1) to (r2, c2) reads p at r2+1 and c2+1.
Read more
- Row- and column-major orderWikipedia
- Summed-area tableWikipedia
- Adjacency matrixWikipedia
- In-place matrix transpositionWikipedia
- The N-dimensional array: internal memory layoutNumPy
Next up
- Sparse TableRow k holds the minimum of every window of length 2^k, each from two half windows above: O(n log n) once.
- Flood FillBFS or DFS on a grid, treating same-coloured neighbours as edges.
- Floyd-WarshallAdmit one stopover vertex per round and relax every pair through it; the matrix converges in n rounds.