Let’s go deep into Prefix Sum (Pre Sum) from a competitive programming perspective.
This is one of the fundamental techniques you’ll repeatedly use in array, string, DP, and number theory problems.
Table of Contents
What is Prefix Sum?
For an array arr[0..n-1], the prefix sum array pre[i] is defined as:
pre[i] = arr[0] + arr[1] + ⋯⋯⋯⋯ +arr[i]That is, the cumulative sum up to index i.
Why use Prefix Sum?
To answer range sum queries efficiently. Without prefix sums, computing sum in [l, r] takes O(n) per query. With prefix sums, each query takes O(1) after O(n) preprocessing.
sum(l,r) = pre[r] − pre[l−1] (l>0)
sum(0,r)=pre[r]Basic Implementation
arr = [2, 4, 6, 8, 10]
n = len(arr)
# Step 1: Build prefix sum
pre = [0] * n
pre[0] = arr[0]
for i in range(1, n):
pre[i] = pre[i-1] + arr[i]
# Step 2: Range query
def range_sum(l, r):
if l == 0:
return pre[r]
return pre[r] - pre[l-1]
print(range_sum(1, 3)) # 18 (4+6+8)
For (l,r), we requires pre[l], that why we are using pre[l-1]
- Preprocessing: O(n)
- Query: O(1)
Variations of Prefix Sum
Competitive programming problems rarely ask just “sum in range”. Instead, prefix sum is extended:
Prefix Sum with Modulo
Useful for problems like counting subarrays divisible by k.
pre[i] = (pre[i−1] + arr[i]) %kPrefix XOR
preXOR[i] = arr[0] ⊕ arr[1] ⊕ ⋯⋯⋯ ⊕ arr[i]
Query: xor(l,r) = preXOR[r] ⊕ preXOR[l−1]2D Prefix Sum (Matrix Problems)
Suppose we have a matrix A of size n × m.
We define the 2D prefix sum matrix P as:
That is, P[i][j] stores the sum of all elements in the submatrix from (1,1) to (i,j) (top-left corner to (i,j)).
Practice
11 12 13
21 22 23
31 32 33
p(11) = 11
p(12) = 11 12
p(13) = 11 12 13
p(21) = 11
21
p(22) = 11 12
21 22
p(23) = 11 12 13
21 22 23
p(31) = 11
21
31
p(32) = 11 12
21 22
31 32
p(33) = 11 12 13
21 22 23
31 32 33 Example
Matrix
e(1,1) e(1,2) e(1,3)
e(2,1) e(2,2) e(2,3)
e(3,1) e(3,2) e(3,3)
Pre Sum Matrix
p(1,1) p(1,2) p(1,3)
p(2,1) p(2,2) p(2,3)
p(3,1) p(3,2) p(3,3)
Row 1
P[1,1] = e(1,1)
P[1,2] = e(1,1) + e(1,2)
P[1,3] = e(1,1) + e(1,2) + e(1,3)
or
P[1,1] = e(1,1)
P[1,2] = P[1,1] + e(1,2)
P[1,3] = P[1,2] + e(1,3)
Row 2
P[2,1] = e(1,1) + e(2,1)
P[2,2] = e(1,1) + e(1,2) + e(2,1) + e(2,2)
P[2,3] = e(1,1) + e(1,2) + e(1,3) + e(2,1) + e(2,2) + e(2,3)
or
P[2,1] = e(1,1) + e(2,1)
P[2,2] = P[2,1] + e(1,2) + e(2,2)
P[2,3] = P[2,2] + e(1,3) + e(2,3)
Row 3
P[3,1] = e(1,1) + e(2,1) + e(3,1)
P[3,2] = e(1,1) + e(1,2) + e(2,1) + e(2,2) + e(3,1) + e(3,2)
P[3,3] = e(1,1) + e(1,2) + e(1,3) + e(2,1) + e(2,2) + e(2,3) + e(3,1) + e(3,2) + e(3,3)
or
P[3,1] = e(1,1) + e(2,1) + e(3,1)
P[3,2] = P[3,1] + e(1,2) + e(2,2) + e(3,2)
P[3,3] = P[3,2] + e(1,3) + e(2,3) + e(3,3)Common mistake
P[i][j] = sum of all elements whose row ≤ i AND column ≤ j.
In words: the rectangle from top-left (1,1) to (i,j).
Not “all previous elements in reading (row-major) order.“
1 2 3
4 5 6
7 8 9
wrong
1 3 6
10 15 21
28 36 45
Right
1 3 6
5 12 21
12 27 45Build Presum Matrix
Wrong approach
For (x1,y1) to (x2,y2):
sum = pre[x2][y2] − pre[x1−1][y2] − pre[x2][y1−1] + pre[x1−1][y1−1]
Finding pre[x2][y2], by taking x1=1 and x2=1
For Presum (1,1) to x2,y2
sum = pre[x2][y2] − pre[0][y2] − pre[x2][0] + pre[0][0]
pre[x2][y2] = pre[x2][y2] − pre[0][y2] − pre[x2][0] + pre[0][0]
But it doesn’t help to calculate as pre[x2][y2] requires pre[x2][y2] Correct Approach
Example P[3,3]
prefix = current element + top strip + left strip - overlap
pre[x,y] = e[x,y] + pre[x-1,y] + pre[x,y-1] - pre[x-1,y-1]Example
P[3,3] = e[3,3] + p[2,3]+p[3,2]- p[2,2]
Code for Pre sum
def build_prefix(matrix):
n, m = len(matrix), len(matrix[0])
P = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
P[i][j] = matrix[i][j]
if i > 0: P[i][j] += P[i-1][j]
if j > 0: P[i][j] += P[i][j-1]
if i > 0 and j > 0: P[i][j] -= P[i-1][j-1]
return P- When i =0 ,pre[i-1,j] ==>pre[-1,j] ==> not valid index , so we need to skip that
- When j =0 ,pre[i,j-1] ==>pre[i,-1] ==> not valid index , so we need to skip that
- When both i=0 and j=0 => pre[-1,-1 ==> not valid index , so we need to skip that
Query
For a matrix mat[m][n], define:
pre[i][j] = sum of submatrix from (0,0) to (i,j)
Query for rectangle (x1,y1) to (x2,y2):
sum = pre[x2][y2] − pre[x1−1][y2] − pre[x2][y1−1] + pre[x1−1][y1−1]
sum = current element - top strip - left strip + overlapNote: Take extra care
- pre[x1−1][y2] : pair x1 and y2
- pre[x2][y1−1] : pair x2 and y1
- current element : Start with too much: the big prefix block.
- top strip : Subtract the top (removes extra rows).
- left strip : Subtract the left (removes extra cols).
- overlap : But then the top-left corner disappeared twice, so add it back once.
- sum: The only part left is the desired rectangle.
Code
def query(P, x1, y1, x2, y2):
res = P[x2][y2]
if x1 > 0: res -= P[x1-1][y2]
if y1 > 0: res -= P[x2][y1-1]
if x1 > 0 and y1 > 0: res += P[x1-1][y1-1]
return resNote: Take extra care
- Bounday condition Decided by x1,y1
Practice
22 to 33
c1 c2 c3 c4
r1 11 12 13 14
r2 21 [22 23] 24
r3 31 [32 33] 34
r4 41 42 43 44
query sum = p(33)-p(13)-p(31)+p(11)
(2,3)→(3,4):
c1 c2 c3 c4
r1 11 12 13 14
r2 21 22 [23 24]
r3 31 32 [33 34]
r4 41 42 43 44
query sum = p(34) - p(14) - p(32) + p(12)
Different approach
It avoids edge checks but shifts indices.
def build_prefix_1_based(matrix):
n, m = len(matrix), len(matrix[0])
P = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
P[i][j] = (matrix[i-1][j-1]
+ P[i-1][j]
+ P[i][j-1]
- P[i-1][j-1])
return P
def query_1_based(P, x1, y1, x2, y2):
"""
Query sum of submatrix [(x1,y1)..(x2,y2)] inclusive.
NOTE: x1,y1,x2,y2 are 1-based coordinates.
"""
return (P[x2][y2]
- P[x1-1][y2]
- P[x2][y1-1]
+ P[x1-1][y1-1])- Pros: Simple clean formula
- Cons: Need to shift indices (original (0,0) → (1,1))
Prefix Minimum / Maximum
- Store running min or max instead of sum.
- Example: “max prefix sum so far” helps in Kadane-like problems.
Practice
Rang Sum Query
LeetCode 303 – Range Sum Query
Brute Force Solution
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
def sumRange(self, left: int, right: int) -> int:
return sum(self.nums[left:right+1])
- Time Complexity: O(n) per query
- If we have many queries, this becomes very slow.
Prefix Sum
The key is to precompute prefix sums.
class NumArray:
def __init__(self, nums: List[int]):
n = len(nums)
self.prefix = [0] * n
self.prefix[0] = nums[0]
for i in range(1, n):
self.prefix[i] = self.prefix[i - 1] + nums[i]
def sumRange(self, left: int, right: int) -> int:
if left == 0:
return self.prefix[right]
return self.prefix[right] - self.prefix[left - 1]Range Sum Query 2D – Immutable
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.matrix = matrix
row = len(self.matrix)
col = len(self.matrix[0])
self.pre_sum =[[0] * (col) for _ in range(row)]
for i in range(row):
for j in range(col):
self.pre_sum[i][j] = self.matrix[i][j]
if i>0:
self.pre_sum[i][j]+= self.pre_sum[i-1][j]
if j>0:
self.pre_sum[i][j]+= self.pre_sum[i][j-1]
if i>0 and j>0:
self.pre_sum[i][j]-= self.pre_sum[i-1][j-1]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
res = self.pre_sum[row2][col2]
if row1 > 0: res -= self.pre_sum[row1-1][col2]
if col1 > 0: res -= self.pre_sum[row2][col1-1]
if row1 > 0 and col1 > 0: res += self.pre_sum[row1-1][col1-1]
return res
More Problems
- LeetCode 1314 – Matrix Block Sum
- LeetCode 560 – Subarray Sum Equals K
- LeetCode 974 – Subarray Sums Divisible by K
- LeetCode 523 – Continuous Subarray Sum
- LeetCode 1442 – Count Triplets That Can Form Two Equal XORs
- LeetCode 1310 – XOR Queries of a Subarray
- LeetCode 370 – Range Addition
- LeetCode 528 – Random Pick with Weight
- LeetCode 1838 – Frequency of the Most Frequent Element
- LeetCode 1658 – Minimum Operations to Reduce X to Zero
- LeetCode 363 – Max Sum of Rectangle No Larger Than K
- LeetCode 1524 – Number of Sub-arrays With Odd Sum
- LeetCode 724 – Find Pivot Index
- LeetCode 862 – Shortest Subarray with Sum at Least K