Overview
Prefix sum is an advanced technique in arrays, but it is relatively easy to learn and has specific application scenarios. It sounds difficult but is actually a simple algorithmic trick to learn.
In Leetcode, problems that can be solved using prefix sums are generally easy or medium-level array problems. They may also appear in hard problems, but in such cases, prefix sums usually act as a helper to reduce repetitive interval calculations and avoid timeout errors in the main algorithm.
I have been emphasizing that prefix sum is a "technique" rather than an "algorithm." This is because the prefix sum is a data preprocessing method used to quickly calculate the sum of elements within a range in an array. It does not solve problems by itself (unless the problem explicitly asks you to generate a prefix sum array).
It is easy to notice: The prefix sum is a typical application of the space-for-time trade-off.
When to Use Prefix Sum
The prefix sum technique is useful for quickly and frequently calculating the sum of elements within a given index range.
In general, prefix sums have three main uses:
- sum(arr[:i]) | Calculate the sum of the first i elements of an array
- sum(arr[i:j]) | Calculate the sum of a subarray
- sum(two_dim_arr[i:j][x:y]) | Quickly calculate the sum of a submatrix in a 2D array
Prefix Sum Array
The implementation of prefix sum follows a consistent pattern, so there are indeed templates to refer to. However, I personally believe that the implementation of the prefix sum itself is not complicated, and its purpose is very clear. It is better to try to fully understand it rather than relying on template code.
First, by solving this problem, which I personally consider to be a "stepping stone to prefix sum" (just my personal opinion 😓) on Leetcode (1480. Running Sum of 1d Array), you can clearly understand how the prefix sum array is generated and what its significance is.
The problem is as follows:
Given an array nums, the formula to calculate the "running sum" of the array is: runningSum[i] = sum(nums[0]...nums[i]). Return the running sum of nums. Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: The running sum is calculated as [1, 1+2, 1+2+3, 1+2+3+4].
The most straightforward solution is undoubtedly brute force: first traverse from [0, N-1], and for each i, calculate sum(arr[:i]).
class Solution(object):
def runningSum(self, nums):
N = len(nums)
preSum = [0] * N
for i in range(N):
curSum = 0
for j in range(i + 1):
curSum += nums[j]
preSum[i] = curSum
return preSum
The time complexity of this solution is O(N^2). It is easy to see that for each calculation of preSum[i], the sum is recalculated starting from position 0, which means for an array of length N, preSum[i] is scanned N - i times repeatedly. These redundant calculations can be completely avoided!
Prefix Sum Solution
While traversing the array in the outer loop, if we want to avoid recalculating the sum of the array from 0 to i, the most direct way is to store it. For the next element, we can directly use the stored value. By doing this, we can use O(1) space to trade for O(N) time, and the entire algorithm can run with O(N) space, reducing the time complexity from O(N^2) to O(N).
class Solution(object):
def runningSum(self, nums):
N = len(nums)
preSum = [0] * N
for i in range(N):
if i == 0:
preSum[i] = nums[i]
continue
preSum[i] = preSum[i-1] + nums[i]
return preSum
This way, the time complexity is reduced to O(N). With the prefix sum array, we can quickly calculate the sum of any subarray.
In this problem, we are only interested in the sum of the subarrays starting from the beginning, but the beauty of the prefix sum is that it can easily calculate the sum of any subarray:
- Sum of subarray [0, i]: preSum[i]
- Sum of subarray [i, j]: preSum[j] - preSum[i-1]
General Problem-Solving Process for Prefix Sum
When to Use the Prefix Sum Algorithm?
As previously mentioned, the most obvious signal for using a prefix sum is: interval sum. If we were to add one more feature, it would be repetition.
Talking about intervals might be confusing because, in the context of arrays, what we typically refer to as an interval is actually a subarray. However, there are many algorithms for handling subarrays, and for continuous subarrays, we often use two pointers or a sliding window approach.
When there are no clear conditions for moving the pointers, you can consider using a prefix sum. Even if you have to exhaustively traverse the array, if there is an opportunity to preprocess with a prefix sum, the overall time complexity will not be too high.
More importantly, if the problem explicitly involves frequently calculating sums, differences, or products of different intervals in an array, using a prefix sum is a safe bet.
Process
To summarize, the prefix sum usually involves only two steps:
- Preprocessing: Traverse the original array to calculate the prefix sum array preSum.
- Usage: As needed, use the prefix sum array to calculate the sum of a specific interval in the array. It is crucial to clearly identify the left and right endpoints of the interval you want to solve, and understand the relationship between the prefix sum array and the original array indices.
2D Array Prefix Sum
Prefix sums in a 1D array are relatively simple, as you only need to subtract values to obtain the sum of any segment in the same dimension. However, array problems often need to consider higher dimensions. In a 2D prefix sum array of M*N, calculating the sum of intervals along any row or column is similar to the 1D prefix sum, which is straightforward. But if we need to calculate the “2D interval sum” for a specific range, will the solution differ significantly?
Let’s use LeetCode problem 304, "Range Sum Query 2D - Immutable," as an example. This problem asks us to calculate the sum of elements in a submatrix within a 2D matrix. The problem is as follows:
Given a 2D matrix matrix, handle multiple requests of the following type: Calculate the total sum of the elements within a subrectangle, with the top-left corner at (row1, col1) and the bottom-right corner at (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 total sum of the elements of the submatrix described by the top-left corner (row1, col1) and bottom-right corner (row2, col2).
Solution 1: Array of Low-Dimensional Prefix Sum Arrays
When we first think about using an M*N 2D prefix sum, we might want to construct a 1D prefix sum array for each of the M rows.
I personally like to call this an "array of low-dimensional prefix sum arrays" (this is not an official term 😓).
This can solve the problem to some extent. At least when traversing the column interval, we can quickly obtain the sum of the interval across rows.
preSumArray = [
[ .... ], // 1D prefix sum array for the first row
[ .... ], // 1D prefix sum array for the second row
...
]
ret = 0
for i in range(start_row, end_row + 1):
col_interval_sum = preSumArray[i][end_col - 1] - preSumArray[i][start_col - 1]
ret += col_interval_sum
Solution 2: Higher-Dimensional Prefix Sum
However, using an "array of low-dimensional prefix sum arrays" to construct a 2D prefix sum array is not optimal. With the same construction time, M one-dimensional prefix sum arrays only reduce costs in one dimension, while an ideal prefix sum array should reduce costs in all dimensions. This requires a higher-dimensional design approach.
Some might wonder, will directly extending the prefix sum array to higher dimensions make the calculations more complex? After all, calculating the sum of a 1D interval in a one-dimensional array seems much simpler and more straightforward than using a 2D prefix sum array to calculate the sum of a 2D region.
The answer is: Yes, it will be more complex. After all, moving to higher dimensions inherently increases complexity. The "array of low-dimensional prefix sum arrays" is essentially a tradeoff between cognitive complexity and time complexity. By sacrificing some algorithmic performance, we allow ourselves to use simpler, low-dimensional calculations, accepting higher time complexity in exchange for lower cognitive load in the algorithm.
However, it seems that “thinking more complexly to reduce performance costs” aligns more with the current mainstream ideology in algorithm development (though it’s not necessarily the only correct approach). The current state of the internet demands handling vast amounts of data, and both algorithms and data structures are designed to save as much as possible. Otherwise, the overflow costs translate into real financial expenses. On the other hand, squeezing human cognitive effort seems to be the more cost-effective option 😭.
Now, we define preSum[i][j] to represent the sum of all elements in the subrectangle from [0,0] to [i,j].
The recursive formula for preSum[i][j] is:
preSum[i][j] = preSum[i−1][j] + preSum[i][j−1] − preSum[i−1][j−1] + matrix[i][j]
The recursive relationship is illustrated below:
S(O,D) = S(O,C) + S(O,B) − S(O,A) + D
Based on this recursive relationship, we can complete the first step: constructing the 2D prefix sum array preSum. preSum[i][j] represents the sum of the elements in the submatrix with the top-left corner at [0,0] and the bottom-right corner at [i,j].
The second step is to use the prefix sum array. We first lock in the large range with the bottom-right corner, and then subtract the extra parts using the top-left corner. The recursive formula is as follows:
preSum[row2][col2] − preSum[row2][col1−1] − preSum[row1−1][col2] + preSum[row1−1][col1−1]
At this point, the algorithm is complete. The complexity summary is as follows:
- Solution 1: Low-Dimensional Prefix Sum Array
- Constructing the prefix sum array: O(N^2)
- Calculating the area of a specific rectangle * N times
- Single calculation: O(N)
- Overall computation: O(N^2)
- Overall complexity: O(N^2) + O(N^2)
- Solution 2: Higher-Dimensional Prefix Sum
- Constructing the prefix sum array: O(N^2)
- Calculating the area of a specific rectangle * N times
- Single calculation: O(1)
- Overall computation: O(N)
- Overall complexity: O(N^2) + O(N)
More Prefix Sum Practice
The prefix sum concept is simple and very practical. However, from an interview perspective, it is crucial to focus on solving problems, as some specifically designed questions require multiple logical steps to figure out even when you are familiar with the prefix sum.
Refer to the following link, which includes many typical examples of prefix sum problems: [Click here]