Problem Description#

Given an integer array nums, call sumRange(left, right) multiple times, returning the sum of elements from index left to right (inclusive). The array itself is never modified.

Example:

1
nums = [-2, 0, 3, -5, 2, -1]
2

3
sumRange(0, 2) → 1      // -2 + 0 + 3
4
sumRange(2, 5) → -1     // 3 + (-5) + 2 + (-1)
5
sumRange(0, 5) → -3     // the entire array

Constraints: 0 <= nums.length <= 10^4, sumRange is called at most 10^4 times.

Why the Naive Solution Doesn’t Pass#

Each sumRange accumulates from left to right, O(n) per call. In the worst case (querying the entire array each time), total complexity is O(n·q), and n = q = 10^4 means 10⁸ additions—rough. And this bottleneck must be paid anew on every query.

The value of prefix sums is “pay once, use forever”: construction scans once in O(n), and afterward each query touches the array only twice—O(1).

The Key: One Extra Slot Makes the Semantics Clean#

Define the prefix array pre with length n + 1:

1
pre[0] = 0
2
pre[i] = nums[0] + nums[1] + ... + nums[i-1]     (1 ≤ i ≤ n)

That is, pre[i] represents “the sum of the first i elements”, a cumulative value over a left-closed, right-open interval [0, i). The extra slot pre[0] = 0 is the glue for the whole approach—it gives the “empty interval” a prefix sum too, so boundaries need no special-casing.

Thus the sum over interval [left, right] (closed interval) can be written as the difference of two prefixes:

1
sum(left, right) = nums[left] + ... + nums[right]
2
                 = pre[right + 1] - pre[left]

Why right + 1? Because pre[right + 1] just barely includes up to nums[right] (the first right + 1 elements = indices 0..right), while pre[left] is exactly the part before left. Head and tail line up.

1
nums:  [ -2,  0,  3, -5,  2, -1 ]
2
index:    0   1   2   3   4   5
3

4
pre:   [ 0, -2, -2,  1, -4, -2, -3 ]
5
index:   0   1   2   3   4   5   6
6
          ↑                       ↑
7
      pre[0]=0            pre[6]=sum of the entire array
8

9
sumRange(2, 5) = pre[6] - pre[2] = -3 - (-2) = -1   ✓
10
                  └ first 6 ┘  └ first 2 ┘

The Three-Part Template#

Prefix sum code is always three parts: build table → query table → (C only) free.

1
① Build table: pre[0] = 0;  for i in 1..n:  pre[i] = pre[i-1] + nums[i-1]
2
② Query: return pre[right + 1] - pre[left]
3
③ Free: (C language) free pre and the object itself

1
#include <stdlib.h>
2

3
typedef struct {
4
    int *pre;   /* pre[i] = sum of nums[0..i-1], length n + 1 */
5
    int n;
6
} NumArray;
7

8
NumArray *numArrayCreate(int *nums, int numsSize) {
9
    NumArray *obj = (NumArray *)malloc(sizeof(NumArray));
10
    obj->n = numsSize;
11
    obj->pre = (int *)malloc((numsSize + 1) * sizeof(int));
12
    obj->pre[0] = 0;                                  /* the extra slot */
13
    for (int i = 0; i < numsSize; i++)
14
        obj->pre[i + 1] = obj->pre[i] + nums[i];      /* sum of the first i+1 elements */
15
    return obj;
16
}
17

18
int numArraySumRange(NumArray *obj, int left, int right) {
19
    return obj->pre[right + 1] - obj->pre[left];      /* one at each end */
20
}
21

22
void numArrayFree(NumArray *obj) {
23
    free(obj->pre);
24
    free(obj);
25
}

1
#include <vector>
2
using namespace std;
3

4
class NumArray {
5
    vector<int> pre;   // pre[i] = sum of nums[0..i-1], length n + 1
6
public:
7
    NumArray(vector<int>& nums) : pre(nums.size() + 1, 0) {
8
        for (int i = 0; i < (int)nums.size(); i++)
9
            pre[i + 1] = pre[i] + nums[i];             // sum of the first i+1 elements
10
    }
11
    int sumRange(int left, int right) {
12
        return pre[right + 1] - pre[left];             // one at each end
13
    }
14
};

1
var NumArray = function (nums) {
2
  // pre[i] = sum of nums[0..i-1], length n + 1
3
  this.pre = new Array(nums.length + 1).fill(0);
4
  for (let i = 0; i < nums.length; i++) {
5
    this.pre[i + 1] = this.pre[i] + nums[i]; // sum of the first i+1 elements
6
  }
7
};
8

9
NumArray.prototype.sumRange = function (left, right) {
10
  return this.pre[right + 1] - this.pre[left]; // one at each end
11
};

Complexity#

Common Pitfalls#

1. Forgetting to allocate one extra slot in pre. Allocating only n in length means pre[right + 1] goes out of bounds when right == n - 1. The extra slot isn’t “waste”—it’s the precondition for writing sumRange(0, x) as a unified formula.
2. Off-by-one in indices. Remember this semantics and you can’t go wrong: pre[i] corresponds to “the first i elements”, and the query is pre[right + 1] - pre[left]. right wants +1, left doesn’t, because the left-closed, right-open interval [left, right+1) is exactly the closed interval [left, right].
3. Confusing the indices of nums[i] and pre[i]. The build-table line is pre[i + 1] = pre[i] + nums[i]—pre is shifted by one relative to nums. Writing pre[i] += nums[i] throws everything off.
4. The problem doesn’t guarantee the interval is non-empty but does guarantee left ≤ right. When left == right, the formula yields nums[left] itself, which is naturally correct—no special-casing needed.

Problem Description#

Given a 2D matrix matrix, call sumRegion(row1, col1, row2, col2) multiple times, returning the sum of elements within the rectangular region formed from the top-left corner (row1, col1) to the bottom-right corner (row2, col2) (all four corners inclusive). The matrix itself will not be modified.

Example:

1
matrix = [[3, 0, 1, 4, 2],
2
          [5, 6, 3, 2, 1],
3
          [1, 2, 0, 1, 5],
4
          [4, 1, 0, 1, 7],
5
          [1, 0, 3, 0, 5]]
6

7
sumRegion(2, 1, 4, 3) → 8     // see the rectangle below
8
sumRegion(1, 1, 2, 2) → 11
9
sumRegion(1, 2, 2, 4) → 12

Constraints: m, n <= 200, sumRegion will be called at most 10^4 times.

From 1D to 2D: Allocate an Extra “Ring”#

In 1D we allocate one extra position (pre[0] = 0); in 2D we allocate one extra row and one extra column: pre of size (m + 1) × (n + 1), with row 0 and column 0 all filled with 0.

Definition:

1
pre[i][j] = sum of the submatrix in the matrix from the top-left corner (0,0) to the bottom-right corner (i-1, j-1)

That is, pre[i][j] represents the rectangle sum formed by “the first i rows and the first j columns.” The extra row 0 / column 0 is the 2D version of pre[0] = 0—it lets queries that “hug the top or left boundary” avoid special-case handling.

Recurrence: One Cell Derived from Three Cells#

The rectangle covered by pre[i][j] can be decomposed into three known regions plus the current cell matrix[i-1][j-1]:

1
① pre[i-1][j]     the rectangle directly above (first i-1 rows, first j columns)
2
② pre[i][j-1]     the rectangle directly to the left (first i rows, first j-1 columns)
3
③ pre[i-1][j-1]   the overlapping part in the upper-left corner — it is counted once each by ①②, so it must be subtracted
4
④ matrix[i-1][j-1] the current cell itself
5

6
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]
7
            └────①────┘ └────②────┘ └─────③─────┘ └──────④──────┘

Why subtract pre[i-1][j-1]? Both ① and ② cover the top-left block “the first i-1 rows and the first j-1 columns,” which gets added twice, so we compensate with one subtraction—this is the inclusion-exclusion principle.

1
      First j-1 columns   j-th column
2
    ┌──────────┬─────┐
3
First  ┌──────────┬─────┐
4
i-1 │    ③     │  ① │
5
row  ├──────────┼─────┤
6
i-th  │    ②     │  ④ │
7
row └──────────┴─────┘

Query: Four Corners, Two Subtractions and One Addition#

The sum of rectangle (r1, c1) ~ (r2, c2) is computed using inclusion-exclusion over four “from origin to some corner” prefix sums:

1
sum(r1, c1, r2, c2)
2
  =   pre[r2 + 1][c2 + 1]     /* large rectangle: up to the bottom-right corner */
3
    - pre[r1][c2 + 1]         /* subtract: the extra part above */
4
    - pre[r2 + 1][c1]         /* subtract: the extra part on the left */
5
    + pre[r1][c1]             /* add: the top-left was subtracted twice, add it back */

Positions of the four corners (note each is a prefix-sum index after ±1):

1
                        c1        c2
2
          0     c1        c2      c2+1
3
       ┌─────┬──────┬─────────┐
4
    0  │     │      │         │
5
       ├─────┼──────┼─────────┤
6
   r1  │     │  ▓▓  │  ▓▓▓▓▓  │   ← pre[r1][*]
7
       ├─────┼──────┼─────────┤
8
   r2  │     │  ▓▓  │  ▓▓▓▓▓  │   ← pre[r2+1][*]
9
       └─────┴──────┴─────────┘
10

11
   Large rectangle  pre[r2+1][c2+1]
12
 − top strip  pre[r1][c2+1]
13
 − left strip  pre[r2+1][c1]
14
 + top-left block  pre[r1][c1]      ← subtracted twice, add it back
15
   ─────────────────────────
16
 = target   sum of ▓▓ cells

Mnemonic: bottom-right +1, top-left no addition; what was subtracted twice gets added back once. That is, at r2 and c2 take +1, at r1 and c1 keep as-is, and the signs from left to right are + − − +.

Three-Part Template#

1
#include <stdlib.h>
2

3
typedef struct {
4
    int **pre;         /* (m+1) x (n+1), one extra ring */
5
    int rows, cols;
6
} NumMatrix;
7

8
NumMatrix *numMatrixCreate(int **matrix, int matrixSize, int *matrixColSize) {
9
    int m = matrixSize, n = matrixColSize[0];
10
    NumMatrix *obj = (NumMatrix *)malloc(sizeof(NumMatrix));
11
    obj->rows = m;
12
    obj->cols = n;
13
    obj->pre = (int **)malloc((m + 1) * sizeof(int *));
14
    for (int i = 0; i <= m; i++)
15
        obj->pre[i] = (int *)calloc(n + 1, sizeof(int));   /* the extra ring, initialized to 0 */
16

17
    for (int i = 1; i <= m; i++)
18
        for (int j = 1; j <= n; j++)
19
            obj->pre[i][j] = obj->pre[i - 1][j] + obj->pre[i][j - 1]
20
                           - obj->pre[i - 1][j - 1] + matrix[i - 1][j - 1];
21
    return obj;
22
}
23

24
int numMatrixSumRegion(NumMatrix *obj, int row1, int col1, int row2, int col2) {
25
    return obj->pre[row2 + 1][col2 + 1]      /* big rectangle */
26
         - obj->pre[row1][col2 + 1]          /* subtract top */
27
         - obj->pre[row2 + 1][col1]          /* subtract left */
28
         + obj->pre[row1][col1];             /* add back top-left */
29
}
30

31
void numMatrixFree(NumMatrix *obj) {
32
    for (int i = 0; i <= obj->rows; i++)
33
        free(obj->pre[i]);
34
    free(obj->pre);
35
    free(obj);
36
}

1
#include <vector>
2
using namespace std;
3

4
class NumMatrix {
5
    vector<vector<int>> pre;   // (m+1) x (n+1), one extra ring
6
public:
7
    NumMatrix(vector<vector<int>>& matrix) {
8
        int m = matrix.size(), n = matrix[0].size();
9
        pre.assign(m + 1, vector<int>(n + 1, 0));
10
        for (int i = 1; i <= m; i++)
11
            for (int j = 1; j <= n; j++)
12
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1]
13
                          - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
14
    }
15
    int sumRegion(int row1, int col1, int row2, int col2) {
16
        return pre[row2 + 1][col2 + 1]   // big rectangle
17
             - pre[row1][col2 + 1]       // subtract top
18
             - pre[row2 + 1][col1]       // subtract left
19
             + pre[row1][col1];          // add back top-left
20
    }
21
};

1
var NumMatrix = function (matrix) {
2
  const m = matrix.length;
3
  const n = matrix[0].length;
4
  // pre is (m+1) x (n+1), the extra ring is 0
5
  this.pre = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
6
  for (let i = 1; i <= m; i++) {
7
    for (let j = 1; j <= n; j++) {
8
      this.pre[i][j] =
9
        this.pre[i - 1][j] + this.pre[i][j - 1] - this.pre[i - 1][j - 1] + matrix[i - 1][j - 1];
10
    }
11
  }
12
};
13

14
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
15
  return (
16
    this.pre[row2 + 1][col2 + 1] - // big rectangle
17
    this.pre[row1][col2 + 1] - // subtract top
18
    this.pre[row2 + 1][col1] + // subtract left
19
    this.pre[row1][col1] // add back top-left
20
  );
21
};

Complexity#

Common Pitfalls#

1. Mixing up the four corners. When stuck, don’t memorize the formula—go back to the inclusion-exclusion diagram above: the big rectangle minus the top strip, minus the left strip; the top-left block was subtracted twice so add it back. Sign order + − − +, only r2 and c2 carry +1.
2. Row 0 / column 0 of pre not set to 0. In C, malloc does not zero-initialize—you must use calloc (or memset) to explicitly zero the extra ring, otherwise you read garbage values when hugging the top/left boundary.
3. matrix[i-1][j-1] written as matrix[i][j]. The table-building loop starts from 1, and the index of pre is 1 larger than that of matrix, so when accessing the original matrix element you must subtract it back.
4. Empty rows or columns. The matrix has at least 1 row and 1 column (guaranteed by the problem constraints), so the C version can safely take matrixColSize[0] directly; but if you wrap it in a general-purpose function yourself, empty matrices need a separate guard.

Limitation 1: No support for dynamic modification#

Prefix sums are a compute-once, read-only structure. If even a single element nums[i] in the original array changes, every pre[i] from i onward is invalidated, and rebuilding is O(n).

1
nums: [ 1, 2, 3, 4, 5 ]        Change nums[0] to 100
2
pre:  [ 0, 1, 3, 6, 10, 15 ]   → pre[1..5] all need to be recomputed, O(n)

Therefore:

This is why the problem repeatedly emphasizes “Immutable”—once it’s mutable, prefix sums are no longer the right answer. Binary Indexed Trees and segment trees are essentially upgraded versions that “let prefix sums be incrementally updated too,” but that’s another topic.

Limitation 2: Only works for operations with an inverse#

The one-dimensional range-sum formula pre[r+1] - pre[l] is essentially using subtraction to remove the part outside the range. So prefix sums only work for operations that have an inverse element:

1
Range minimum ≠ prefixMin[r+1] - prefixMin[l]     ← Completely wrong, prefix min cannot be subtracted out

When you need range min / max / gcd, the weapons to switch to are:

One-line criterion: only when you can write a “subtract/cancel” relationship like 区间结果 = f(前缀, 前缀) is it prefix sums’ turn.

Limitation 3: Accumulation overflows and loses precision#

Prefix sums are accumulated quantities, much larger in magnitude than the original array, so the overflow risk is on a different scale entirely.

• Integer overflow: summing 10^5 numbers on the order of 10^9 can reach 10^14—32-bit int blows up long before that. When building prefix sums you must use long long (C / C++) / BigInt (JS), even if the problem’s original array is int.
• Floating-point error: pre[r+1] - pre[l] is the subtraction of two large numbers, and subtracting large numbers causes loss of significant digits. If the array elements are floating-point, subtracting long prefixes can yield noticeably biased results, and precision-sensitive scenarios need a different approach.
• Two dimensions amplify faster: in the immutable matrix, each cell of pre is a rectangular sum, totaling the sum of m·n elements—the overflow threshold is even lower than in one dimension, so wide types are even more essential.

1
// ❌ the original array is int, but the prefix sum must be long long
2
vector<int> pre(n + 1, 0);
3
pre[i + 1] = pre[i] + nums[i];          // accumulating on the order of 10^9 over tens of thousands of times overflows
4

5
// ✅
6
vector<long long> pre(n + 1, 0);
7
pre[i + 1] = pre[i] + nums[i];

Limitation 4: Loses the internal structure of the range#

Prefix sums only remember “the cumulative value up to some point,” trading for O(1) queries at the cost of being unable to see the distribution inside the range. Two classes of problems are therefore out of reach:

• Those needing internal extrema: range maximum, longest consecutive subsegment… the answers to internal-information questions can’t be derived from “the difference of two prefixes” (see Limitation 2).
• Those relying on monotonicity: prefix sums are monotonic only when all elements are non-negative. Once there are negative numbers in the array, pre is no longer monotonic, and tricks like “binary search on prefix sums to find the answer” fail on the spot—for example, subarrays summing to K: when elements include negatives, you can’t rely on two pointers / binary search, and must honestly use a hash map + prefix sums to count occurrences (see the Principles article for details).

1
nums = [1, -1, 1, -1]     pre = [0, 1, 0, 1, 0]   ← alternates up and down, not monotonic
2
nums = [1,  2, 3,  4]     pre = [0, 1, 3, 6, 10]  ← monotonically increasing

Limitations summary#

Remember prefix sums’ positioning: it’s a specialized accelerator for “static, invertible range aggregation,” not a general-purpose data structure. Before using it, ask three questions—Will the data change? Is the operation invertible? Will the values overflow? Only when all three pass should you bring out prefix sums.