Prefix sum is a technique where we precompute cumulative sums so we can answer “what’s the sum from index i to index j?” in O(1) time. Without it, every range sum query takes O(n). With it, we do O(n) work once, and then every query is instant.
Think of it like keeping a running total. Instead of adding up numbers every time someone asks, we maintain a list of “sum so far” values and just subtract to get any range.
Building a Prefix Sum Array
Given an array nums, the prefix sum array prefix[i] = sum of all elements from index 0 to i.
function buildPrefixSum(nums) {
const prefix = new Array(nums.length);
prefix[0] = nums[0];
for (let i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] + nums[i]; // running total
}
return prefix;
}
console.log(buildPrefixSum([2, 4, 1, 3, 5])); // [2, 6, 7, 10, 15]def build_prefix_sum(nums):
prefix = [0] * len(nums)
prefix[0] = nums[0]
for i in range(1, len(nums)):
prefix[i] = prefix[i - 1] + nums[i] # running total
return prefix
print(build_prefix_sum([2, 4, 1, 3, 5])) # [2, 6, 7, 10, 15]public static int[] buildPrefixSum(int[] nums) {
int[] prefix = new int[nums.length];
prefix[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] + nums[i]; // running total
}
return prefix;
}
// [2, 4, 1, 3, 5] → [2, 6, 7, 10, 15]Time: O(n) to build, O(1) per query after that.
Range Sum Query
Once we have the prefix sum array, getting the sum of any range [left, right] is just one subtraction:
sum(left, right) = prefix[right] - prefix[left - 1]If left is 0, then sum(0, right) = prefix[right].
function rangeSum(prefix, left, right) {
if (left === 0) return prefix[right];
return prefix[right] - prefix[left - 1];
}
const prefix = buildPrefixSum([2, 4, 1, 3, 5]);
console.log(rangeSum(prefix, 1, 3)); // 4 + 1 + 3 = 8
console.log(rangeSum(prefix, 0, 4)); // 2 + 4 + 1 + 3 + 5 = 15
console.log(rangeSum(prefix, 2, 2)); // 1 (single element)def range_sum(prefix, left, right):
if left == 0:
return prefix[right]
return prefix[right] - prefix[left - 1]
prefix = build_prefix_sum([2, 4, 1, 3, 5])
print(range_sum(prefix, 1, 3)) # 4 + 1 + 3 = 8
print(range_sum(prefix, 0, 4)) # 2 + 4 + 1 + 3 + 5 = 15
print(range_sum(prefix, 2, 2)) # 1 (single element)public static int rangeSum(int[] prefix, int left, int right) {
if (left == 0) return prefix[right];
return prefix[right] - prefix[left - 1];
}
// prefix = [2, 6, 7, 10, 15]
// rangeSum(prefix, 1, 3) → 10 - 2 = 8 ✓
// rangeSum(prefix, 0, 4) → 15 ✓Pro tip: Some people prefer building the prefix array with an extra 0 at the beginning:
prefix[0] = 0, prefix[1] = nums[0], .... This eliminates theleft === 0edge case because the formula becomesprefix[right + 1] - prefix[left]always.
Subarray Sum Equals K
This is one of the most popular prefix sum interview problems (LeetCode 560). Given an array and a target k, find the number of subarrays that sum to k.
The key insight: if prefixSum[j] - prefixSum[i] = k, then the subarray from i+1 to j sums to k. So we need to count how many times prefixSum[j] - k has appeared before.
We use a hash map to track how many times each prefix sum has occurred.
function subarraySum(nums, k) {
const prefixCount = new Map(); // prefix sum → count
prefixCount.set(0, 1); // empty prefix has sum 0
let sum = 0;
let count = 0;
for (const num of nums) {
sum += num;
// if (sum - k) exists, there's a subarray ending here with sum k
if (prefixCount.has(sum - k)) {
count += prefixCount.get(sum - k);
}
prefixCount.set(sum, (prefixCount.get(sum) || 0) + 1);
}
return count;
}
console.log(subarraySum([1, 1, 1], 2)); // 2 ([1,1] at two positions)
console.log(subarraySum([1, 2, 3], 3)); // 2 ([1,2] and [3])def subarray_sum(nums, k):
prefix_count = {0: 1} # prefix sum → count
current_sum = 0
count = 0
for num in nums:
current_sum += num
# if (sum - k) exists, there's a subarray ending here with sum k
if current_sum - k in prefix_count:
count += prefix_count[current_sum - k]
prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
return count
print(subarray_sum([1, 1, 1], 2)) # 2
print(subarray_sum([1, 2, 3], 3)) # 2public static int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1); // empty prefix has sum 0
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
if (prefixCount.containsKey(sum - k)) {
count += prefixCount.get(sum - k);
}
prefixCount.merge(sum, 1, Integer::sum);
}
return count;
}
// [1, 1, 1] with k=2 → 2Time: O(n), Space: O(n) — the hash map + prefix sum combo turns an O(n²) problem into O(n).
Difference Array Technique
Prefix sum is for range queries. The difference array is for range updates.
Imagine we have an array of zeros and we need to add 5 to every element from index 2 to 5. Then add 3 to every element from index 1 to 4. Doing this naively is O(n) per update. With a difference array, each update is O(1).
The idea: instead of updating every element in the range, we mark the start and end+1 of the range. Then we compute the prefix sum at the end to get the final array.
function applyRangeUpdates(n, updates) {
const diff = new Array(n + 1).fill(0); // difference array
for (const [left, right, value] of updates) {
diff[left] += value; // start adding here
diff[right + 1] -= value; // stop adding after here
}
// build result from difference array (prefix sum)
const result = new Array(n);
result[0] = diff[0];
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}
// Array of size 5, two updates: add 5 to [1,3], add 3 to [2,4]
console.log(applyRangeUpdates(5, [[1, 3, 5], [2, 4, 3]]));
// [0, 5, 8, 8, 3]def apply_range_updates(n, updates):
diff = [0] * (n + 1) # difference array
for left, right, value in updates:
diff[left] += value # start adding here
diff[right + 1] -= value # stop adding after here
# build result from difference array (prefix sum)
result = [0] * n
result[0] = diff[0]
for i in range(1, n):
result[i] = result[i - 1] + diff[i]
return result
# Array of size 5, two updates: add 5 to [1,3], add 3 to [2,4]
print(apply_range_updates(5, [[1, 3, 5], [2, 4, 3]]))
# [0, 5, 8, 8, 3]public static int[] applyRangeUpdates(int n, int[][] updates) {
int[] diff = new int[n + 1]; // difference array
for (int[] update : updates) {
diff[update[0]] += update[2]; // start adding here
diff[update[1] + 1] -= update[2]; // stop adding after here
}
// build result from difference array (prefix sum)
int[] result = new int[n];
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}
// n=5, updates=[[1,3,5],[2,4,3]] → [0, 5, 8, 8, 3]Each update is O(1). Final reconstruction is O(n). So for q updates on an array of size n, it’s O(n + q) instead of O(n * q).
When to Use These Techniques
| Technique | Use When | Complexity |
|---|---|---|
| Prefix Sum | Many range sum queries on a static array | O(n) build + O(1) per query |
| Prefix Sum + Hash Map | Count subarrays with a target sum | O(n) time + O(n) space |
| Difference Array | Many range update operations, query at the end | O(1) per update + O(n) to reconstruct |
In simple language, prefix sum is about doing homework upfront so we don’t repeat work later. We spend O(n) once to build the prefix array, and then every range query is free (O(1)). The difference array flips this idea — instead of querying ranges efficiently, it lets us update ranges efficiently. Both are must-know patterns for coding interviews.