Prefix Sum Array Technique

The prefix sum technique is suitable for quickly and frequently calculating the sum of elements within a given index range.

Prefix Sum in One-Dimensional Arrays

Let's look at a sample problem, LeetCode Problem 303: "Range Sum Query - Immutable", which asks you to calculate the sum of elements within an array range. This is a standard prefix sum problem:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

// The problem requires you to implement such a class
class NumArray {

    public NumArray(int[] nums) {}
    
    // Query the cumulative sum of the closed interval [left, right]
    public int sumRange(int left, int right) {}
}

// The problem requires you to implement such a class
class NumArray {
public:
    NumArray(vector<int>& nums) {}
    
    // Query the accumulated sum of the closed interval [left, right]
    int sumRange(int left, int right) {}
};

# The problem requires you to implement such a class
class NumArray:
    
    def __init__(self, nums: List[int]):
        pass
        
    # Query the accumulated sum of the closed interval [left, right]
    def sumRange(self, left: int, right: int) -> int:
        pass

// The problem requires you to implement such a class
type NumArray struct {}

func Constructor(nums []int) NumArray {}

// Query the cumulative sum of the closed interval [left, right]
func (this *NumArray) SumRange(left int, right int) int {}

// The problem requires you to implement such a class
var NumArray = function(nums) {
  
  this.nums = nums;
  
  // Query the accumulated sum of the closed interval [left, right]
  this.sumRange = function(left, right) {}
  
};

The sumRange function needs to calculate and return the sum of elements within an index range. Those unfamiliar with prefix sums might write code like this:

class NumArray {
	private int[] nums;
	public NumArray(int[] nums) {
		this.nums = nums;
	}

	public int sumRange(int left, int right) {
		// use for loop to sum
		int sum = 0;
		for (int i = left; i <= right; i++) {
			sum += nums[i];
		}
		return sum;
	}
}

This solution requires a for-loop traversal each time the sumRange function is called, resulting in a time complexity of $O(N)$. Since the sumRange function may be called very frequently, this makes the algorithm inefficient.

The correct approach is to use the prefix sum technique for optimization, reducing the time complexity of the sumRange function to $O(1)$:

class NumArray {
    // prefix sum array
    private int[] preSum;

    // input an array to construct the prefix sum
    public NumArray(int[] nums) {
        // preSum[0] = 0, to facilitate the calculation of accumulated sums
        preSum = new int[nums.length + 1];
        // calculate the accumulated sums of nums
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    // query the sum of the closed interval [left, right]
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

#include <vector>

class NumArray {
    // prefix sum array
    std::vector<int> preSum;

    // input an array to construct the prefix sum
    public:
    NumArray(std::vector<int>& nums) {
        // preSum[0] = 0, to facilitate the calculation of accumulated sums
        preSum.resize(nums.size() + 1);
        // calculate the accumulated sums of nums
        for (int i = 1; i < preSum.size(); i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    // query the sum of the closed interval [left, right]
    int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
};

class NumArray:
    # prefix sum array
    def __init__(self, nums: List[int]):
        # input an array to construct the prefix sum
        # preSum[0] = 0, to facilitate the calculation of accumulated sums
        self.preSum = [0] * (len(nums) + 1)
        # calculate the accumulated sums of nums
        for i in range(1, len(self.preSum)):
            self.preSum[i] = self.preSum[i - 1] + nums[i - 1]

    # query the sum of the closed interval [left, right]
    def sumRange(self, left: int, right: int) -> int:
        return self.preSum[right + 1] - self.preSum[left]

type NumArray struct {
    // prefix sum array
    PreSum []int
}

// input an array to construct the prefix sum
func Constructor(nums []int) NumArray {
    // PreSum[0] = 0, to facilitate the calculation of accumulated sums
    preSum := make([]int, len(nums)+1)
    // calculate the accumulated sums of nums
    for i := 1; i < len(preSum); i++ {
        preSum[i] = preSum[i-1] + nums[i-1]
    }
    return NumArray{PreSum: preSum}
}

// query the sum of the closed interval [left, right]
func (this *NumArray) SumRange(left int, right int) int {
    // The following line includes the missing comment:
    // PreSum[0] = 0, to facilitate the calculation of accumulated sums
    return this.PreSum[right+1] - this.PreSum[left] // Here we are using the prefix sum property, no need to repeat the comment here.
}

var NumArray = function(nums) {
    // prefix sum array
    let preSum = new Array(nums.length + 1).fill(0);

    // preSum[0] = 0, to facilitate the calculation of accumulated sums
    preSum[0] = 0;

    // input an array to construct the prefix sum
    for (let i = 1; i < preSum.length; i++) {
        // calculate the accumulated sums of nums
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }

    this.preSum = preSum;
};

// query the sum of the closed interval [left, right]
NumArray.prototype.sumRange = function(left, right) {
    return this.preSum[right + 1] - this.preSum[left];
};

The core idea is to create a new array preSum, where preSum[i] stores the cumulative sum of nums[0..i-1]. For example, $10 = 3 + 5 + 2$:

Using this preSum array, if we want to find the sum of all elements in the index range [1, 4], we can calculate it as preSum[5] - preSum[1].

Thus, the sumRange function only needs to perform one subtraction operation, avoiding the for-loop calls each time, with a worst-case time complexity of $O(1)$.

This technique is widely used in real life. For example, if your class has several students, each with a final exam score (out of 100), you can implement an API that returns the number of students whose scores fall within a given range.

You can first use counting sort to calculate how many students have each specific score, then use the prefix sum technique to implement the score range query API:

// stores all the students' scores
int[] scores = new int[]{...};
// the full mark of the test paper is 100 points
int[] count = new int[100 + 1];

// record the number of students for each score
for (int score : scores) {
    count[score]++;
}
// construct the prefix sum array
for (int i = 1; i < count.length; i++) {
    count[i] = count[i] + count[i-1];
}

// use the prefix sum array 'count' to query score segments

// query how many students scored between 80 and 90
int result = count[90] - count[80];

Next, let's see how the prefix sum approach is applied in a two-dimensional array.

Prefix Sum in a 2D Matrix

This is LeetCode problem 304, "Range Sum Query 2D - Immutable", which is similar to the previous problem. The previous problem asked you to calculate the sum of elements in a subarray, while this one requires you to calculate the sum of elements in a submatrix of a 2D matrix:

304. Range Sum Query 2D - Immutable | LeetCode |  🟠

Given a 2D matrix matrix, handle multiple queries of the following type:

• Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

• NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
• int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

You must design an algorithm where sumRegion works on O(1) time complexity.

Example 1:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -104 <= matrix[i][j] <= 104
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• At most 104 calls will be made to sumRegion.

The problem is from LeetCode 304. Range Sum Query 2D - Immutable.

Of course, you could use a nested for loop to traverse the matrix, but this would increase the time complexity of the sumRegion function, and reduce the efficiency of your algorithm.

Note that the sum of elements in any submatrix can be transformed into the sum of elements in several larger matrices surrounding it:

These four larger matrices all share a common characteristic: their top-left corners are at the origin (0, 0).

The better approach to this problem, similar to the prefix sum in one-dimensional arrays, is to maintain a two-dimensional preSum array that records the sum of elements in matrices with the origin as the vertex. Thus, the sum of elements in any submatrix can be calculated using several addition and subtraction operations:

class NumMatrix {
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) return;
        // construct the prefix sum matrix
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // calculate the sum of elements for each matrix [0, 0, i, j]
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
            }
        }
    }

    // calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    public int sumRegion(int x1, int y1, int x2, int y2) {
        // the sum of the target matrix is obtained by operations on four adjacent matrices
        return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
    }
}

#include <vector>

class NumMatrix {
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    std::vector<std::vector<int>> preSum;

public:
    NumMatrix(std::vector<std::vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if (m == 0 || n == 0) return;
        // construct the prefix sum matrix
        preSum.resize(m + 1, std::vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // calculate the sum of elements for each matrix [0, 0, i, j]
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
            }
        }
    }
    
    // calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    int sumRegion(int x1, int y1, int x2, int y2) {
        // the sum of the target matrix is obtained by operations on four adjacent matrices
        return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
    }
};

class NumMatrix:
    # preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    def __init__(self, matrix: List[List[int]]):
        m = len(matrix)
        n = len(matrix[0])
        if m == 0 or n == 0:
            return
        # construct the prefix sum matrix
        self.preSum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # calculate the sum of elements for each matrix [0, 0, i, j]
                self.preSum[i][j] = (self.preSum[i - 1][j] + self.preSum[i][j - 1] +
                                     matrix[i - 1][j - 1] - self.preSum[i - 1][j - 1])

    # calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    def sumRegion(self, x1: int, y1: int, x2: int, y2: int) -> int:
        # the sum of the target matrix is obtained by operations on four adjacent matrices
        return (self.preSum[x2 + 1][y2 + 1] - self.preSum[x1][y2 + 1] -
                self.preSum[x2 + 1][y1] + self.preSum[x1][y1])

type NumMatrix struct {
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    preSum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix)
    if m == 0 {
        return NumMatrix{}
    }
    n := len(matrix[0])
    if n == 0 {
        return NumMatrix{}
    }
    // construct the prefix sum matrix
    preSum := make([][]int, m+1)
    for i := range preSum {
        preSum[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            // calculate the sum of elements for each matrix [0, 0, i, j]
            preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1]
        }
    }
    return NumMatrix{preSum: preSum}
}

// calculate the sum of elements in the submatrix [x1, y1, x2, y2]
func (this *NumMatrix) SumRegion(x1, y1, x2, y2 int) int {
    // the sum of the target matrix is obtained by operations on four adjacent matrices
    return this.preSum[x2+1][y2+1] - this.preSum[x1][y2+1] - this.preSum[x2+1][y1] + this.preSum[x1][y1]
}

var NumMatrix = function(matrix) {
    let m = matrix.length, n = matrix[0].length;
    // preSum[i][j] records the sum of elements in the matrix [0, 0, i-1, j-1]
    this.preSum = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
    if (m == 0 || n == 0) return;
    // construct the prefix sum matrix
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // calculate the sum of elements for each matrix [0, 0, i, j]
            this.preSum[i][j] = this.preSum[i-1][j] + this.preSum[i][j-1] + matrix[i - 1][j - 1] - this.preSum[i-1][j-1];
        }
    }
};

NumMatrix.prototype.sumRegion = function(x1, y1, x2, y2) {
    // calculate the sum of elements in the submatrix [x1, y1, x2, y2]
    // the sum of the target matrix is obtained by operations on four adjacent matrices
    return this.preSum[x2+1][y2+1] - this.preSum[x1][y2+1] - this.preSum[x2+1][y1] + this.preSum[x1][y1];
};

In this way, the time complexity of the sumRegion function is optimized to $O(1)$ using the prefix sum technique, which is a typical "space for time" trade-off.

The prefix sum technique is explained here. This algorithm technique is easy for those who understand it and difficult for those who don't. In practical applications, you need to cultivate your mental flexibility to quickly identify a prefix sum problem when you see one.

Further Expansion

The prefix sum technique explained in this article uses a precomputed preSum array to quickly calculate the sum of elements within a given index range. However, it is not limited to summation; it can also be used for quickly computing products and other scenarios.

Moreover, prefix sum arrays are often combined with other data structures or algorithmic techniques. I will explain these combinations in High-Frequency Prefix Sum Exercises along with relevant exercises.

However, the prefix sum technique has several limitations.

First Limitation: The prerequisite for using the prefix sum technique is that the original array nums does not change.

If an element in the original array changes, the values in the preSum array after that element become invalid, requiring $O(n)$ time to recalculate the preSum array, which is similar to the brute-force method.

Second Limitation: The prefix sum technique is only applicable in scenarios with inverse operations.

For example, in summation scenarios, if you know $x + 6 = 10$, you can deduce $x = 10 - 6 = 4$. Similarly, in product scenarios, if you know $x * 6 = 12$, you can deduce $x = 12 / 6 = 2$. This is known as having an inverse operation, which allows the use of the prefix sum technique.

However, some scenarios do not have inverse operations. For example, in maximum value scenarios, if you know $max(x, 8) = 8$, you cannot deduce the value of $x$.

To address both issues simultaneously, more advanced data structures are required. The most general solution is the Segment Tree, which will be explained in detail in the data structure design chapter.