Prefix Sum Array Technique

The prefix sum technique is suitable for quickly and frequently calculating the sum of elements within an indexed range.

Prefix Sum in One-Dimensional Arrays

Let's look at an example 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 who have not learned prefix sums might write the following code:

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;
// the full mark of the test paper is 100 points
int[] count = new int[100 + 1];
// record how many students have each score
for (int score : scores)
    count[score]++;
// construct the prefix sum
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

Next, let's take a look at how the prefix sum concept is applied in a two-dimensional array.

Prefix Sum in 2D Matrix

This is LeetCode problem 304 "Range Sum Query 2D - Immutable". It is similar to the previous problem, where you were asked to calculate the sum of elements in a subarray. This problem 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.

Of course, you can use a nested for loop to traverse this matrix, but this will make the time complexity of the sumRegion function high, reducing the efficiency of your algorithm.

Note that the sum of any submatrix can be transformed into operations involving the sums of a few larger matrices surrounding it:

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

A better approach to this problem, similar to the prefix sum in a one-dimensional array, is to maintain a two-dimensional preSum array to specifically record the sum of elements in matrices with the origin as the top vertex. This allows you to calculate the sum of elements in any submatrix with a few 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];
};

Thus, 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.

This concludes the discussion on the prefix sum technique. It can be said that this algorithm is easy for those who understand it but challenging for others. In practical applications, it's essential to develop flexibility in thinking to identify prefix sum problems at a glance.

Further Exploration

The prefix sum technique explained in this article utilizes a precomputed preSum array to quickly calculate the sum of elements within an index range. However, it is not limited to summation; it can also be used to quickly calculate the maximum, minimum, product, etc., within a range.

Additionally, prefix sum arrays are often combined with other data structures or algorithm techniques. I will explain these combinations through exercises in Frequent Problems with Prefix Sum Techniques.

Another important point: The prerequisite for using prefix sum techniques is that the original array nums must remain unchanged.

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, which is not much different from the standard brute-force method.

Therefore, in scenarios where array elements can change, we should use a data structure like a Segment Tree to handle range queries and dynamic updates.