The 1D prefix sum is the foundation of all prefix sum techniques. It's elegant, powerful, and once you understand the template, you can solve an entire class of range query problems in minutes.
It transforms O(n) range sum queries into O(1) lookups. It's used in dozens of LeetCode problems. And the template is so simple, you can write it from memory in an interview.
But here's the key: understanding why the template works and handling edge cases correctly is what separates those who memorize code from those who truly master the pattern.
This guide will teach you the complete 1D prefix sum template, when to apply it, common patterns, and how to avoid the mistakes that trip up most developers.
Use 1D prefix sum when:
Template:
# Build prefix sum
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
# Query sum from index i to j (inclusive)
sum_range = prefix[j + 1] - prefix[i]Time: O(n) preprocessing, O(1) per query
Space: O(n)
A prefix sum array stores cumulative sums at each position. prefix[i] represents the sum of all elements from index 0 to i-1 in the original array.
Key insight: To get the sum of any range [i, j], we subtract two prefix sums:
sum(i, j) = prefix[j+1] - prefix[i]Visual example:
Original: [3, 1, 4, 1, 5, 9, 2]
Index: 0 1 2 3 4 5 6
Prefix: [0, 3, 4, 8, 9, 14, 23, 25]
Index: 0 1 2 3 4 5 6 7
↑
Always start with 0
Query: sum(2, 5) = sum of elements from index 2 to 5
= prefix[6] - prefix[2]
= 23 - 4
= 19
Verify: 4 + 1 + 5 + 9 = 19 ✓The mathematical foundation is simple:
sum(0, j) = nums[0] + nums[1] + ... + nums[j]
sum(0, i-1) = nums[0] + nums[1] + ... + nums[i-1]
Therefore:
sum(i, j) = sum(0, j) - sum(0, i-1)
By storing cumulative sums, we can compute any range sum with one subtraction.
Notice we start the prefix array with 0. This is critical because:
sum(0, j) would require special handling.prefix[j+1] - prefix[i] works for all cases, including when i = 0.Example without padding (buggy):
# Wrong approach
prefix = [nums[0]]
for i in range(1, len(nums)):
prefix.append(prefix[-1] + nums[i])
# Now sum(0, j) = prefix[j], but sum(i, j) = ???
# Need special case for i = 0, prone to errorsExample with padding (correct):
# Correct approach
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
# sum(i, j) = prefix[j+1] - prefix[i] works for ALL casesclass RangeSumQuery:
"""
Template for 1D prefix sum range queries.
Time Complexity:
- __init__: O(n)
- sumRange: O(1)
Space Complexity: O(n)
"""
def __init__(self, nums: List[int]):
# Edge case: empty array
if not nums:
self.prefix = [0]
return
# Build prefix sum array with padding
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
def sumRange(self, left: int, right: int) -> int:
"""
Calculate sum of elements from index left to right (inclusive).
Args:
left: Start index (0-indexed)
right: End index (0-indexed, inclusive)
Returns:
Sum of nums[left] + nums[left+1] + ... + nums[right]
"""
# Formula: prefix[right+1] - prefix[left]
return self.prefix[right + 1] - self.prefix[left]
# Usage
nums = [1, 2, 3, 4, 5]
obj = RangeSumQuery(nums)
print(obj.sumRange(1, 3)) # 2 + 3 + 4 = 9
print(obj.sumRange(0, 4)) # 1 + 2 + 3 + 4 + 5 = 15
print(obj.sumRange(2, 2)) # 3class RangeSumQuery {
/**
* @param {number[]} nums
*/
constructor(nums) {
if (!nums || nums.length === 0) {
this.prefix = [0];
return;
}
// Build prefix sum array
this.prefix = [0];
for (const num of nums) {
this.prefix.push(this.prefix[this.prefix.length - 1] + num);
}
}
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
sumRange(left, right) {
return this.prefix[right + 1] - this.prefix[left];
}
}
// Usage
const nums = [1, 2, 3, 4, 5];
const obj = new RangeSumQuery(nums);
console.log(obj.sumRange(1, 3)); // 9
console.log(obj.sumRange(0, 4)); // 15
console.log(obj.sumRange(2, 2)); // 3class RangeSumQuery {
private int[] prefix;
/**
* Initialize with input array.
* Time: O(n), Space: O(n)
*/
public RangeSumQuery(int[] nums) {
if (nums == null || nums.length == 0) {
prefix = new int[1];
return;
}
// Build prefix sum array
prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
/**
* Calculate sum of elements from left to right (inclusive).
* Time: O(1)
*/
public int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left];
}
}
// Usage
int[] nums = {1, 2, 3, 4, 5};
RangeSumQuery obj = new RangeSumQuery(nums);
System.out.println(obj.sumRange(1, 3)); // 9
System.out.println(obj.sumRange(0, 4)); // 15
System.out.println(obj.sumRange(2, 2)); // 3Given an integer array nums, handle multiple queries of the following type:
nums between indices left and right inclusive.Example:
Input: nums = [-2, 0, 3, -5, 2, -1]
Query 1: sumRange(0, 2) → -2 + 0 + 3 = 1
Query 2: sumRange(2, 5) → 3 + (-5) + 2 + (-1) = -1
Query 3: sumRange(0, 5) → -2 + 0 + 3 + (-5) + 2 + (-1) = -3class NumArray:
def __init__(self, nums: List[int]):
# Build prefix sum
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]
# Test
nums = [-2, 0, 3, -5, 2, -1]
obj = NumArray(nums)
print(obj.sumRange(0, 2)) # 1
print(obj.sumRange(2, 5)) # -1
print(obj.sumRange(0, 5)) # -3Prefix array construction:
nums: [-2, 0, 3, -5, 2, -1]
prefix: [0, -2, -2, 1, -4, -2, -3]Query sumRange(2, 5):
= prefix[6] - prefix[2]
= -3 - (-2)
= -1
Verify: 3 + (-5) + 2 + (-1) = -1 ✓Time:
Space: O(n) for prefix array
Comparison with brute force:
Find the pivot index where the sum of elements to the left equals the sum of elements to the right.
Example:
Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
Left sum = 1 + 7 + 3 = 11
Right sum = 5 + 6 = 11def pivotIndex(nums: List[int]) -> int:
"""
Find pivot index using running sum (prefix sum).
Time: O(n), Space: O(1)
"""
total = sum(nums)
left_sum = 0
for i, num in enumerate(nums):
# Right sum = total - left_sum - current element
right_sum = total - left_sum - num
if left_sum == right_sum:
return i
# Update left sum for next iteration
left_sum += num
return -1
# Test
print(pivotIndex([1, 7, 3, 6, 5, 6])) # 3
print(pivotIndex([1, 2, 3])) # -1
print(pivotIndex([2, 1, -1])) # 0We maintain a running sum (which is essentially a prefix sum computed on-the-fly):
Trace for [1, 7, 3, 6, 5, 6]:
total = 28
i=0: left=0, right=28-0-1=27, 0≠27
i=1: left=1, right=28-1-7=20, 1≠20
i=2: left=8, right=28-8-3=17, 8≠17
i=3: left=11, right=28-11-6=11, 11=11 ✓ return 3Notice we don't need to store the entire prefix array—we can compute the running sum on-the-fly, using O(1) space instead of O(n).
Return an array where answer[i] is the product of all elements except nums[i], without using division.
Example:
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation:
answer[0] = 2 × 3 × 4 = 24
answer[1] = 1 × 3 × 4 = 12
answer[2] = 1 × 2 × 4 = 8
answer[3] = 1 × 2 × 3 = 6def productExceptSelf(nums: List[int]) -> List[int]:
"""
Use prefix and suffix products.
Time: O(n), Space: O(1) excluding output array
"""
n = len(nums)
result = [1] * n
# Build prefix products (left to right)
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Build suffix products (right to left) and multiply
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
# Test
print(productExceptSelf([1, 2, 3, 4])) # [24, 12, 8, 6]
print(productExceptSelf([-1, 1, 0, -3, 3])) # [0, 0, 9, 0, 0]Step 1: Prefix products (left to right)
nums: [1, 2, 3, 4]
result: [1, 1, 2, 6] ← product of all elements to the leftStep 2: Suffix products (right to left)
result: [1, 1, 2, 6]
suffix: [24, 12, 4, 1] ← product of all elements to the right
result: [24, 12, 8, 6] ← multiply prefix × suffixThis is the product variant of prefix sum, applying the same cumulative logic to multiplication instead of addition.
nums = []
obj = RangeSumQuery(nums)
# Should not crash, prefix = [0]Handling:
if not nums:
self.prefix = [0]
returnnums = [5]
obj = RangeSumQuery(nums)
print(obj.sumRange(0, 0)) # Should return 5Trace:
prefix = [0, 5]
sumRange(0, 0) = prefix[1] - prefix[0] = 5 - 0 = 5 ✓nums = [0, 0, 0, 0]
obj = RangeSumQuery(nums)
print(obj.sumRange(1, 3)) # Should return 0Trace:
prefix = [0, 0, 0, 0, 0]
sumRange(1, 3) = prefix[4] - prefix[1] = 0 - 0 = 0 ✓nums = [-1, -2, -3]
obj = RangeSumQuery(nums)
print(obj.sumRange(0, 2)) # Should return -6Trace:
prefix = [0, -1, -3, -6]
sumRange(0, 2) = prefix[3] - prefix[0] = -6 - 0 = -6 ✓Key insight: Prefix sum handles negative numbers perfectly. No special logic needed.
In languages like Java, be aware of integer overflow:
// If sum might exceed Integer.MAX_VALUE, use long
private long[] prefix;❌ Wrong:
# Forgetting to add 1 to right index
sum_range = prefix[right] - prefix[left]Why it's wrong: This gives you the sum from left to right-1, not including right.
✅ Correct:
sum_range = prefix[right + 1] - prefix[left]See guide: Off-by-One Errors
❌ Wrong:
prefix = []
for num in nums:
if prefix:
prefix.append(prefix[-1] + num)
else:
prefix.append(num)Why it's wrong: Makes the formula inconsistent and requires special handling for ranges starting at index 0.
✅ Correct:
prefix = [0] # Always start with 0
for num in nums:
prefix.append(prefix[-1] + num)❌ Wrong:
# Modifying nums in place
for i in range(1, len(nums)):
nums[i] += nums[i-1]Why it's wrong: Destroys the original array, which might be needed later.
✅ Correct:
# Create separate prefix array
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)❌ Wrong:
prefix = [0] * len(nums) # Wrong size!Why it's wrong: Prefix array should be size n+1, not n.
✅ Correct:
prefix = [0] * (len(nums) + 1)
# Or build dynamically
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)Problem: Answer q range sum queries on array of size n.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute force | O(q × n) | O(1) | q = 1, n small |
| Prefix sum | O(n + q) | O(n) | q ≥ 2, n large |
| Segment tree | O(n + q log n) | O(n) | Frequent updates |
Break-even point: When q ≥ 2, prefix sum is already faster than brute force.
Master 1D prefix sum with these problems:
Beginner:
Intermediate:
4. Product of Array Except Self (#238) - Prefix product
5. Left and Right Sum Differences (#2574) - Prefix and suffix sums
6. Find the Middle Index in Array (#1991) - Similar to pivot index
Advanced:
7. Range Sum Query - Mutable (#307) - Compare with segment tree
8. Maximum Subarray (#53) - Compare with Kadane's algorithm
Q: Why do we start with prefix[0] = 0?
A: It simplifies the formula and handles ranges starting from index 0 without special cases. See Off-by-One Errors.
Q: Can I use prefix sum if the array has negative numbers?
A: Yes! Prefix sum works perfectly with negative numbers. No special handling needed.
Q: What if I need to update the array?
A: If you have frequent updates:
Q: Is prefix sum the same as sliding window?
A: No. Prefix sum is for range queries (sum from i to j). Sliding window is for finding subarrays with certain properties. See Prefix Sum vs Sliding Window.
Q: Can I save space by not storing the prefix array?
A: For some problems (like Find Pivot Index), you can use a running sum with O(1) space. But for multiple queries, you need to store the prefix array.
The 1D prefix sum template is a fundamental pattern that every software engineer should master.
Key principles:
sum(i, j) = prefix[j+1] - prefix[i]The template:
# Build
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
# Query
sum_range = prefix[right + 1] - prefix[left]When to use:
Master this template, and you'll solve range query problems with confidence. For more advanced patterns, see the complete prefix sum guide, 2D prefix sum, and prefix sum + hash map.
Next time you see "range sum query," reach for the 1D prefix sum template.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free