2D range-max DP and doubling on shapes

Some problems ask for the maximum value over every square region of a given size inside a larger grid, or over every sub-shape of a size that keeps growing. Checking each region from scratch costs too much once the grid or the shape gets large. Doubling fixes this: build the answer for size 2, then size 4, then size 8, each time combining two already-solved pieces of half the size instead of starting over.

2D range maximum queries

In a 2D grid, you often need the maximum value inside a square region. A sparse table built over the grid answers these queries in constant time after O(N^2 log N) preprocessing.

The sparse table stores table[k][i][j] as the maximum over the 2^k by 2^k square whose top-left corner is (i, j). Layer 0 is the grid itself, one cell per square. Layer k combines four squares from layer k - 1: the one at (i, j) and the three squares that reach it by shifting half the current size right, down, or both.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7    grid = []8    idx = 19    for i in range(n):10        row = [int(input_data[idx + j]) for j in range(n)]11        grid.append(row)12        idx += n13
14    # table[k] holds the sparse table for 2^k by 2^k squares.15    # table[k][i][j] is the max over rows i..i+2^k-1 and columns j..j+2^k-1.16    max_k = 017    while (1 << (max_k + 1)) <= n:18        max_k += 119
20    table = [grid]21    for k in range(1, max_k + 1):22        half = 1 << (k - 1)23        prev = table[k - 1]24        span = len(prev) - half25        layer = []26        for i in range(span):27            row = []28            for j in range(span):29                row.append(max(30                    prev[i][j],31                    prev[i + half][j],32                    prev[i][j + half],33                    prev[i + half][j + half],34                ))35            layer.append(row)36        table.append(layer)37
38    def query(r1, c1, r2, c2):39        # Decompose the square region into two overlapping power-of-2 squares40        # per side and take the max of the four corners.41        side = r2 - r1 + 142        k = side.bit_length() - 143        size = 1 << k44        t = table[k]45        return max(46            t[r1][c1],47            t[r2 - size + 1][c1],48            t[r1][c2 - size + 1],49            t[r2 - size + 1][c2 - size + 1],50        )51
52    print(query(0, 0, n - 1, n - 1))53
54
55if __name__ == "__main__":56    main()

3
1 2 3
4 5 6
7 8 9

9

To answer a query for a square region, find the largest power of 2 that fits inside its side length. Read off the layer for that power at all four corners of the region: top-left, bottom-left, top-right and bottom-right. Their maximum is the answer, because those four squares of the chosen size cover the whole region between them.

Combining overlapping squares

A region that is not itself a power of 2 in size still gets covered by four overlapping power-of-2 squares. A 3x3 region, for example, is covered by four overlapping 2x2 squares, one anchored at each corner. Every cell in the 3x3 region lies inside at least one of those four squares.

The overlap is harmless because the operation is maximum, not sum. A cell that falls inside two of the four squares gets compared twice, but a value does not become larger for being read more than once. Summing regions this way would double-count the overlap; taking the maximum does not.

Preparation and complexity

Building the sparse table takes O(N^2 log N) time and space: N^2 cells per layer, and about log N layers. That holds comfortably for N up to a few thousand. Each query then costs O(1): one bit_length() call to find the power of 2, and four array reads.

Doubling on a triangle

The same idea carries over to shapes that are not rectangular. Picture a triangle stored as a 2D array where row i holds i + 1 elements: row 0 is the single apex, and each row below has one more entry than the row above it. You want the maximum sum along any path from the apex down to the base.

A triangle of 8 rows splits into three triangles of 4 rows each: the top one (rows 0-3), and two at the bottom (rows 4-7, one built from the left half of each row and one from the right half). Row 4 is where the two bottom triangles share cells, the same kind of overlap the square grid had.

Compute the answer for every size-4 triangle first. Combining three finished size-4 triangles into the size-8 answer costs only the work of joining them at the shared row, not the work of solving the size-8 triangle from scratch. Doubling the size again to 16 reuses the size-8 answers the same way. Each doubling step costs O(N^2) instead of the O(N^3) a size-by-size solution would need, because you never recompute a smaller triangle you already have.

Common mistakes

The most common error is losing track of the shared cells when combining sub-shapes. A cell inside the overlap belongs to more than one piece being combined, and the combining step must read it from just one of them, not add its value in twice.

A second mistake is rebuilding the sparse table inside the query loop instead of once before it. The table takes O(N^2 log N) to build; if you rebuild it for every query you will time out, even though each individual query is cheap.

A third pitfall is assuming 32-bit range for the grid values. If a value can reach 10^9 and you sum several of them, the running total can pass what a 32-bit integer holds. Python's integers do not overflow, so this only bites you if you later port the idea to a language with fixed-width integers.

Why this works and its cost

The maximum operation makes overlaps harmless: reading a cell more than once during a combine step does not change its value, so double-covering a boundary costs nothing. That property is what lets you decompose a shape into overlapping pieces instead of hunting for a partition with no shared cells at all.

The cost is the table you build to get there. O(N^2 log N) space and preprocessing time holds up to a few thousand cells on a side. Past that, the memory alone becomes the limit before the time does. When a problem's constraints push N into the tens of thousands, check whether a smaller subtask still fits this approach: solving that subtask in full is worth more than an incomplete attempt at the whole problem.