Definition: What Is Prefix Sum Technique?
Prefix Sum Technique precomputes cumulative sums of array elements, allowing O(1) range sum queries. A prefix sum array stores the sum of all elements from index 0 to the current index. To get the sum from index i to j, you use prefix[j] - prefix[i-1].
Prefix sum reduces time complexity from O(n) per query to O(1) per query after O(n) preprocessing. Instead of calculating the sum from scratch each time, you precompute all cumulative sums once, then answer queries instantly using simple subtraction.
This technique is especially powerful when you have multiple range sum queries on the same array. The preprocessing cost is paid once, and all subsequent queries are O(1), making it much more efficient than calculating sums repeatedly.
Key Point: Prefix sum precomputes cumulative sums in O(n) time, then answers range sum queries in O(1) time using prefix[j] - prefix[i-1]. Ideal for multiple queries on static arrays. Reduces O(n) per query to O(1) per query.
What: Understanding Prefix Sum
Understanding how prefix sum works:
Real-Life Analogy: Running Total
Prefix sum is like keeping a running total of your expenses:
Just like a running total, prefix sum keeps cumulative sums so you can answer queries instantly.
Prefix Sum Array
Prefix sum array stores cumulative sum from index 0 to current index. prefix[i] = sum of arr[0] to arr[i]. Built in O(n) time by iterating once. Example: arr = [1,2,3,4,5], prefix = [1,3,6,10,15]. Each element is sum of all previous elements plus current element.
Example: prefix[2] = arr[0] + arr[1] + arr[2] = 1 + 2 + 3 = 6
Range Sum Query
To get sum from index i to j: prefix[j] - prefix[i-1]. If i=0, just use prefix[j]. This gives O(1) query time. Without prefix sum, you'd need to iterate from i to j, giving O(n) time. Prefix sum makes range queries instant after preprocessing.
Example: Sum from index 1 to 3 = prefix[3] - prefix[0] = 10 - 1 = 9
Prefix Sum Array Visualization
Original Array
Prefix Sum Array
prefix[i] = sum of arr[0] to arr[i]
Range Sum Query: Sum from index 1 to 3
Important: Prefix sum array stores cumulative sums. Range sum query uses prefix[j] - prefix[i-1] for O(1) time. Preprocessing takes O(n), but all queries are O(1). Ideal for multiple queries on static arrays.
When: When to Use Prefix Sum
Use prefix sum in these situations:
Use Prefix Sum When:
- Multiple range queries: Many queries on same array
- Range sum queries: Sum of subarray from i to j
- Static array: Array doesn't change frequently
- Need O(1) queries: Fast query time required
- Cumulative problems: Running totals, cumulative sums
Avoid Prefix Sum When:
- Single query: Overhead not worth it
- Frequent updates: Array changes often
- Memory constrained: O(n) extra space needed
- Other operations: Need min/max, not just sum
- 2D arrays: Need 2D prefix sum (more complex)
Common Scenario: Use prefix sum for multiple range sum queries on static arrays. Avoid prefix sum for single queries or frequently-changing arrays. Prefix sum is ideal when preprocessing cost is amortized over many queries.
How To: Implement Prefix Sum with Examples
Learn to implement prefix sum with examples:
Example 1: Basic Prefix Sum Implementation
Create prefix sum array and answer range queries:
# Prefix Sum Implementation
def build_prefix_sum(arr):
n = len(arr)
prefix = [0] * n
# Build prefix sum array
prefix[0] = arr[0]
for i in range(1, n):
prefix[i] = prefix[i-1] + arr[i]
return prefix
def range_sum(prefix, i, j):
# Sum from index i to j (inclusive)
if i == 0:
return prefix[j]
return prefix[j] - prefix[i-1]
# Example usage
arr = [1, 2, 3, 4, 5]
prefix = build_prefix_sum(arr)
print(prefix) # Output: [1, 3, 6, 10, 15]
# Range queries
print(range_sum(prefix, 0, 2)) # Sum from 0 to 2: 1+2+3 = 6
print(range_sum(prefix, 1, 3)) # Sum from 1 to 3: 2+3+4 = 9
print(range_sum(prefix, 2, 4)) # Sum from 2 to 4: 3+4+5 = 12
# How it works:
# prefix[0] = arr[0] = 1
# prefix[1] = prefix[0] + arr[1] = 1 + 2 = 3
# prefix[2] = prefix[1] + arr[2] = 3 + 3 = 6
# ...
# range_sum(1, 3) = prefix[3] - prefix[0] = 10 - 1 = 9Prefix Sum Building Process
Example 2: Range Sum Query Problem
Answer multiple range sum queries efficiently:
# Problem: Answer multiple range sum queries
# Array: [2, 8, 3, 9, 6, 5, 4]
# Queries: sum from index 0 to 2, 1 to 3, 2 to 6
def answer_range_queries(arr, queries):
# Build prefix sum array
n = len(arr)
prefix = [0] * n
prefix[0] = arr[0]
for i in range(1, n):
prefix[i] = prefix[i-1] + arr[i]
# Answer queries
results = []
for i, j in queries:
if i == 0:
results.append(prefix[j])
else:
results.append(prefix[j] - prefix[i-1])
return results
# Example usage
arr = [2, 8, 3, 9, 6, 5, 4]
queries = [(0, 2), (1, 3), (2, 6)]
results = answer_range_queries(arr, queries)
print(results) # Output: [13, 20, 27]
# Query 1: sum(0,2) = 2+8+3 = 13
# Query 2: sum(1,3) = 8+3+9 = 20
# Query 3: sum(2,6) = 3+9+6+5+4 = 27
# Time Complexity: O(n + m) where n=array size, m=number of queries
# Without prefix sum: O(n*m) - much slower!Best Practice: Build prefix array in O(n) by iterating once. Answer queries in O(1) using prefix[j] - prefix[i-1]. Handle edge case when i=0 (use prefix[j] directly). Prefix sum reduces O(n) per query to O(1) per query, making it ideal for multiple queries.
Why: Why Prefix Sum Matters
Prefix sum matters for these reasons:
O(1) Query Time
Prefix sum provides O(1) query time after O(n) preprocessing. Instead of O(n) per query, you get instant answers. For m queries, total time is O(n + m) instead of O(n*m). This makes prefix sum extremely efficient for multiple queries.
Simple Implementation
Prefix sum is simple to implement. Just build prefix array once, then answer queries with simple subtraction. The logic is straightforward: prefix[j] - prefix[i-1]. This makes prefix sum easy to understand and implement in interviews.
Common Interview Topic
Prefix sum is a common coding interview topic. Interviewers frequently ask about range sum queries, subarray problems, and cumulative sums. Understanding prefix sum is essential for technical interviews and coding challenges.
Foundation for Advanced Techniques
Prefix sum is the foundation for advanced techniques: 2D prefix sum, difference array, and other range query problems. Understanding 1D prefix sum helps understand these more complex techniques. Many problems can be solved with prefix sum.
Important: Prefix sum matters because it provides O(1) query time, is simple to implement, is a common interview topic, and is the foundation for advanced techniques. Prefix sum is one of the most important techniques for range query problems.
Frequently Asked Questions
What is prefix sum technique?
Prefix sum technique precomputes cumulative sums of array elements, allowing O(1) range sum queries. Prefix sum array stores sum of all elements from index 0 to current index. To get sum from index i to j, use prefix[j] - prefix[i-1]. This reduces time complexity from O(n) per query to O(1) per query after O(n) preprocessing. Example: array [1,2,3,4,5] has prefix sum [1,3,6,10,15].
How does prefix sum work?
Prefix sum works by: 1) Create prefix array where prefix[i] = sum of elements from 0 to i, 2) To get sum from i to j, calculate prefix[j] - prefix[i-1] (or prefix[j] if i=0), 3) This gives O(1) query time after O(n) preprocessing. Prefix array is built once, then all queries are O(1). Example: prefix[2] = 6 (1+2+3), prefix[4] = 15 (1+2+3+4+5), sum from 2 to 4 = prefix[4] - prefix[1] = 15 - 3 = 12.
When to use prefix sum technique?
Use prefix sum for: range sum queries (sum of subarray from i to j), multiple queries on same array (preprocessing pays off), problems requiring cumulative sums, and when you need O(1) query time. Prefix sum is great when you have many queries on static or rarely-changing arrays. Avoid prefix sum for single query (overhead not worth it) or when array changes frequently.
What is the time complexity of prefix sum?
Prefix sum has O(n) time complexity for preprocessing (building prefix array) and O(1) time complexity for each range sum query. Space complexity is O(n) for storing prefix array. For m queries, total time is O(n + m) instead of O(n*m) without prefix sum. This makes prefix sum very efficient for multiple queries.
What are the advantages of prefix sum?
Advantages: O(1) query time after preprocessing, efficient for multiple queries, simple to implement, reduces time complexity from O(n) to O(1) per query. Disadvantages: O(n) extra space, O(n) preprocessing time, not efficient for single query, array should be static or rarely change. Prefix sum is ideal when you have many range sum queries.