Imagine writing down how much money you saved each day. Someone asks how much you saved from Tuesday to Thursday. You can add those three days. But what if they ask about hundreds of different date ranges?
You would repeat many of the same additions. Prefix sum lets you do the addition once and reuse it.
You only need to understand arrays, indexes, addition, and a loop to begin. We will learn the basic idea first, then build towards interview patterns.
1. What does “prefix sum” mean?
A prefix is the beginning of something. A prefix sum is the sum of values from the beginning of an array up to a chosen position.
For values = [2, 4, 1, 3, 5], the running totals are:
- After
2:2. - After
4:2 + 4 = 6. - After
1:6 + 1 = 7. - After
3:7 + 3 = 10. - After
5:10 + 5 = 15.
That is the whole idea: keep adding the next value to the total you already have.
A small convention that prevents many bugs
In this article, we use a prefix array with one extra position:
values = [2, 4, 1, 3, 5] prefix = [0, 2, 6, 7, 10, 15]
prefix[i] means the sum of the first i elements. It does not mean the sum through array index i.
Therefore, prefix[0] = 0: before reading any elements, the sum is zero. prefix[3] = 7 is the sum of array indexes 0, 1, and 2.
InsightKeep this sentence in mind: prefix[i] stores the sum before array index i. At
i = n, it stores the whole array’s sum.
2. Why is it useful?
A subarray is a continuous piece of an array. You cannot skip elements. In [2, 4, 1, 3, 5], [4, 1, 3] is a subarray; [4, 3] is not.
Suppose we want the sum from index 1 to index 3, including both ends:
values[1] + values[2] + values[3] = 4 + 1 + 3 = 8
The total before index 4 is 10. The total before index 1 is 2. Subtract the part we do not want:
sum from index 1 through index 3 = prefix[4] - prefix[1] = 10 - 2 = 8
For zero-based, inclusive indexes left and right, the formula is:
rangeSum(left, right) = prefix[right + 1] - prefix[left]
Why right + 1? Because prefix counts elements. To include array index 3, we need the first four elements.
From repeated work to reusable work
If there are n values and q queries:
| Approach | Preparation | One range query | All queries |
|---|---|---|---|
| Add each range again | None | O(n) in the worst case | O(n × q) |
| Build prefix sums once | O(n) | O(1) | O(n + q) |
O(1) means the query needs a fixed amount of work: read two totals and subtract. It does not mean literally zero time. The prefix array needs O(n) extra memory. This static range-query technique is also explained in the USACO Guide’s introduction to prefix sums.
For only one total-sum query, a simple loop is usually enough. Prefix sums become especially useful when totals need to be reused.
3. Build and use prefix sums in Java
Here is a complete program you can run. It uses long for totals because adding many int values can overflow an int.
public class PrefixSumBasics {
static long[] buildPrefix(int[] values) {
long[] prefix = new long[values.length + 1];
for (int i = 0; i < values.length; i++) {
prefix[i + 1] = prefix[i] + values[i];
}
return prefix;
}
// Both left and right are included in the answer.
static long rangeSum(long[] prefix, int left, int right) {
int n = prefix.length - 1;
if (left < 0 || right < left || right >= n) {
throw new IllegalArgumentException("Invalid range");
}
return prefix[right + 1] - prefix[left];
}
public static void main(String[] args) {
int[] values = {2, 4, 1, 3, 5};
long[] prefix = buildPrefix(values);
System.out.println(rangeSum(prefix, 1, 3)); // 8
System.out.println(rangeSum(prefix, 0, 4)); // 15
System.out.println(rangeSum(prefix, 2, 2)); // 1
}
}The extra zero makes ranges starting at index 0 work without a special case. An empty input creates [0], but there is no valid nonempty range to query.
Dry run: follow the Java assignments
Keep the meaning of the index beside each assignment. We have processed i elements before reading values[i], so writing prefix[i+1] extends the processed prefix by one element.
| i | values[i] | Java assignment | New total |
|---|---|---|---|
| 0 | 2 | prefix[1] = prefix[0] + 2 |
2 |
| 1 | 4 | prefix[2] = prefix[1] + 4 |
6 |
| 2 | 1 | prefix[3] = prefix[2] + 1 |
7 |
| 3 | 3 | prefix[4] = prefix[3] + 3 |
10 |
| 4 | 5 | prefix[5] = prefix[4] + 5 |
15 |
For the first invocation, the range guard accepts left=1 and right=3. The return statement reads prefix[4] and prefix[1], then calculates 10 - 2 = 8. It does not add the range’s elements again.
Try before moving on: What is the sum from index 2 to index 4? Use prefix[5] - prefix[2]: 15 - 6 = 9.
4. How do I recognize a prefix sum question?
Do not look only for the words “prefix sum.” Look at what the question asks you to reuse.
Clue A: Many sums over an unchanged array
“Answer the sum between L and R for many queries.” This is the most direct clue. Build a prefix array and subtract two totals.
Clue B: A continuous piece must have a target sum
“Count subarrays whose sum is K” or “Find the longest subarray with sum K.” Think about the difference between the current running total and an earlier total. A hash map often helps find that earlier total quickly.
Clue C: Negative numbers are allowed
Negative values do not break prefix sums. They do break the usual reasoning that extending a sliding window always increases its sum. For example, extending [5] with -3 reduces the sum to 2.
Negative numbers are a clue to reconsider sliding windows—not proof that every such problem needs prefix sums.
Clue D: Equal counts or divisibility
“Equal numbers of zeros and ones” can become a zero-sum problem after replacing 0 with -1. “Subarray sum divisible by K” can become a problem about matching remainders of prefix totals.
Clue E: Repeated rectangle sums
If the input is a grid and questions ask for the sum inside different rectangles, consider two-dimensional prefix sums.
Ask these three questions
- Am I working with a continuous range?
- Can its answer be expressed using a total up to one boundary minus a total up to another?
- What do I need to remember about earlier totals: existence, frequency, or an index?
If these questions fit, prefix sums are worth trying. They are not a universal answer for every array problem.
5. The identity behind subarray patterns
Let current be the running sum at the current position. Let earlier be a running sum before the subarray starts.
subarraySum = current - earlier
If the subarray must sum to k:
current - earlier = k earlier = current - k
So at each position, ask: Have I already seen a prefix sum equal to current - k?
You do not always need to build a whole prefix array. For these scanning patterns, one running total plus a map is enough.
6. Pattern: Count subarrays with sum K
Consider [1, 1, 1] with k = 2. There are two valid subarrays: indexes 0..1 and 1..2. We count positions, even if the values look identical.
Store how many times each earlier prefix sum has appeared.
| Value read | Current sum | Needed earlier sum: current − 2 | Earlier matches | Total answers |
|---|---|---|---|---|
| First 1 | 1 | −1 | 0 | 0 |
| Second 1 | 2 | 0 | 1 | 1 |
| Third 1 | 3 | 1 | 1 | 2 |
Before the loop, record prefix sum 0 once. It represents the empty prefix before the first element. Without it, we would miss a valid subarray starting at index 0.
import java.util.HashMap;
import java.util.Map;
public class CountSubarrays {
static long countWithSum(int[] values, long k) {
Map<Long, Long> frequency = new HashMap<>();
frequency.put(0L, 1L);
long current = 0;
long count = 0;
for (int value : values) {
current += value;
// Count earlier boundaries before recording this boundary.
count += frequency.getOrDefault(current - k, 0L);
frequency.put(current,
frequency.getOrDefault(current, 0L) + 1);
}
return count;
}
public static void main(String[] args) {
System.out.println(countWithSum(new int[]{1, 1, 1}, 2)); // 2
System.out.println(countWithSum(new int[]{1, -1, 0}, 0)); // 3
System.out.println(countWithSum(new int[]{0, 0, 0}, 0)); // 6
}
}Time is expected O(n) with a hash map; space is O(n) in the worst case. long count matters too: an array of n zeros has n × (n + 1) / 2 zero-sum subarrays.
Why check before inserting? If you insert the current prefix first and k = 0, you would match the current boundary with itself. That is an empty subarray, not a valid nonempty answer.
Why a frequency map, not a set? [0, 0] has three zero-sum subarrays. Multiple earlier boundaries can have the same prefix total. A set would forget how many boundaries exist.
7. Pattern: Longest subarray with sum K
The equation stays the same, but the map stores an earliest index, not a count.
If the current index is i and the earlier matching prefix occurred at j, the subarray is j + 1..i, with length i - j. To maximize the length, keep the smallest possible j.
import java.util.HashMap;
import java.util.Map;
public class LongestSubarray {
static int longestWithSum(int[] values, long k) {
Map<Long, Integer> earliest = new HashMap<>();
earliest.put(0L, -1);
long current = 0;
int longest = 0;
for (int i = 0; i < values.length; i++) {
current += values[i];
Integer previous = earliest.get(current - k);
if (previous != null) {
longest = Math.max(longest, i - previous);
}
earliest.putIfAbsent(current, i);
}
return longest;
}
public static void main(String[] args) {
int[] values = {1, -1, 5, -2, 3};
System.out.println(longestWithSum(values, 3)); // 4
}
}The first four values sum to 3. The initial entry (0, -1) lets that range have length 3 - (-1) = 4. Do not overwrite an earlier occurrence: that can shorten a later answer.
Expected time is O(n) and space is O(n). See the focused article on Longest Subarray with Sum K for another explanation.
8. Other common prefix sum patterns
You do not need to master all of these today. First understand range sums, then counting and longest-length problems.
| Question asks for… | What to remember | Key idea |
|---|---|---|
| Sum of a fixed range | Prefix array | Subtract the left boundary from the right boundary |
| Whether a sum-K subarray exists | Set of previous sums | Look for current − K |
| Number of sum-K subarrays | Frequency of previous sums | Every matching earlier boundary adds an answer |
| Longest sum-K subarray | Earliest index of each sum | Earliest start gives longest length |
| Shortest exact-sum K subarray | Latest index of each sum | Latest valid start gives shortest length |
| Equal zeros and ones | Earliest index of transformed sum | Treat 0 as −1 and 1 as +1; seek sum 0 |
| Sum divisible by K | Frequency of prefix remainders | Equal remainders give a divisible difference |
| Sum of a rectangle | 2D prefix table | Add and subtract corner totals |
The shortest sum at least K problem is different from shortest sum exactly K. With negative values, “at least K” commonly needs prefix sums plus a monotonic deque, not just the latest-index map.
Equal numbers of zeros and ones
Transform [0, 1, 0, 1] into [-1, 1, -1, 1]. A transformed subarray sums to zero exactly when it contains equal numbers of zeros and ones. Now use the longest-zero-sum pattern.
Subarray sums divisible by K
If two prefix sums leave the same remainder after division by positive k, their difference is divisible by k.
For example, 14 % 5 = 4 and 4 % 5 = 4; their difference 10 is divisible by 5.
Java can produce a negative remainder for a negative number. For a positive divisor, normalize using:
long remainder = Math.floorMod(current, k); // k must be positiveSeed remainder 0 with frequency 1. At each step, add the number of earlier matching remainders, then record the new remainder.
Two-dimensional prefix sums
For a grid, prefix[r][c] can store the sum of the first r rows and first c columns. Include a zero row and a zero column.
To build it:
prefix[r + 1][c + 1] = grid[r][c]
+ prefix[r][c + 1]
+ prefix[r + 1][c]
- prefix[r][c]The top and left totals overlap, so subtract the overlap once. For an inclusive rectangle from (r1, c1) to (r2, c2):
answer = prefix[r2 + 1][c2 + 1]
- prefix[r1][c2 + 1]
- prefix[r2 + 1][c1]
+ prefix[r1][c1]Building the table takes O(rows × columns) time and space; each rectangle query takes O(1) time. Explore this later using the USACO Guide’s 2D prefix sum explanation.
9. Prefix sum or sliding window?
These techniques sometimes solve similar questions, but they use different information.
| Situation | A useful starting point |
|---|---|
| Many range-sum queries on unchanged data | Prefix array |
| Sum-K subarrays with positive and negative values | Prefix sum plus map |
| One maximum-sum window of fixed length | Sliding window with a rolling sum |
| Longest sum-K range with nonnegative values | Sliding window can work |
| Maximum sum over any nonempty subarray | Kadane’s algorithm is usually simpler |
| Values change frequently between sum queries | Consider a Fenwick tree or segment tree |
For nonnegative values, extending a window cannot decrease its sum; removing its leftmost value cannot increase it. That makes certain two-pointer rules possible. Negative numbers remove that guarantee.
Also, counting exact-sum windows in the presence of zeros needs care: several starting positions may produce the same sum. A basic window that increments the answer once per ending position can miss answers.
10. When should I avoid ordinary prefix sums?
- Frequent updates: Changing
values[i]invalidates all later prefix totals. An ordinary prefix array is best for static data. More advanced structures can support updates. - Range minimum or maximum: You cannot generally subtract two prefix minimums to recover a range minimum. Addition works here because subtraction can remove the unwanted contribution.
- Only one simple sum: A normal loop may be clearer and use less memory.
- Noncontiguous choices: A subset or subsequence problem is not automatically a subarray-prefix problem.
Prefix XOR is a related technique for XOR queries because XOR can cancel an earlier prefix. It is not the same operation as prefix addition.
11. Common mistakes and how to catch them
- Mixing conventions. Here,
prefix[i]means the firstivalues. Do not mix it with a tutorial that stores the sum through indexi. - Missing the extra zero. It makes ranges beginning at index zero work naturally.
- Forgetting the initial map entry. Counting needs
(0, 1); longest length needs(0, -1). - Using a set for counting. Repeated prefix totals must retain their frequencies.
- Replacing earliest indexes. For longest length, use
putIfAbsent. - Recording before checking. That can count an empty range when the target is zero.
- Overflowing totals or answers. Use
longfor prefix totals and potentially large counts. Check the actual constraints;longis larger, not unlimited. - Using an unnormalized negative remainder. Use
Math.floorModwith a positive divisor. - Assuming prefix totals always increase. They can decrease when values are negative.
Test at least: a one-element array, a range starting at zero, all zeros, negative values, repeated prefix totals, and no matching subarray.
12. Practice in this order
Start with understanding, not speed. Predict a few prefix totals on paper before running your code.
- Build the prefix array for
[3, -2, 5, 1]. Answer:[0, 3, 1, 6, 7]. - Find the sum of indexes
1..3. Answer:7 - 3 = 4. - Solve Range Sum Query — Immutable.
- Solve Find Pivot Index: compare the sum before an index with the sum after it.
- Work through Subarray Sum Equals K in Java, then try the linked LeetCode problem yourself.
- Revisit Longest Subarray with Sum K.
- Try Contiguous Array for the zero-to-minus-one transformation.
- Try Subarray Sums Divisible by K.
- Move to Range Sum Query 2D — Immutable.
For each question, say out loud: What does my prefix represent, what earlier value do I need, and what must the map store?
13. The idea to remember
Prefix sums are not a collection of formulas to memorize. They are a way to save work you have already done.
Build a total from the beginning. Remove an earlier total to reveal the continuous piece between two boundaries.
For direct range queries, store those totals in an array. For subarray searches, remember earlier totals in a set or map. The question—existence, count, or length—decides what information you store.
If arrays themselves are still new, start with Array Fundamentals in Java and return here afterwards.
Practice next
Next lessonSubarray Sum Equals K in Java: From Brute Force to Prefix SumCount subarrays with sum K using a prefix sum and frequency map, with beginner-friendly diagrams, a dry run, Java solutions, and common mistakes.