Hints — p32 Range Sum Query 2D Immutable

Read one at a time.

Hint 1 — Recall 1D. 1D prefix sum: prefix[i] = nums[0]+...+nums[i-1]. Then sum(l, r) = prefix[r+1] - prefix[l]. Build O(N), query O(1). Now generalize to 2D.

Hint 2 — 2D prefix. Define P[r][c] = sum of all cells (i, j) with 0 ≤ i < r and 0 ≤ j < c. So P has shape (R+1) × (C+1) with P[0][*] = P[*][0] = 0.

Hint 3 — Inclusion-exclusion (the formula). For a query rectangle from (r1, c1) to (r2, c2) inclusive: $$\text{answer} = P[r_2{+}1][c_2{+}1] - P[r_1][c_2{+}1] - P[r_2{+}1][c_1] + P[r_1][c_1]$$ Start with full top-left rectangle, subtract top, subtract left, add back the double-subtracted top-left corner.

Hint 4 — The “+1 border” trick. Allocating (R+1) × (C+1) with the first row and column zeroed eliminates the if r1 == 0 / if c1 == 0 branches that wreck candidates. Every prefix-sum problem benefits from this.

Hint 5 — Build recurrence. $$P[r][c] = \text{matrix}[r-1][c-1] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]$$ Same inclusion-exclusion at build time. Total O(R·C).

If still stuck: see solution.py. The class is ~20 lines.