Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Prefix Sum in Java: A Beginner's Guide to Range Sums and Subarray Patterns

Learn prefix sums from scratch with visual examples, Java code, recognition clues, common subarray patterns, and mistakes to avoid.

BasicsArraysPattern: prefix sum, hashing

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:

Worked example · read from top to bottom
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.

Building prefix sums for 2, 4, 1, 3, 5: begin with zero and add each value to get 0, 2, 6, 7, 10, 15.

Insight

Keep 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:

Worked example · read from top to bottom
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:

Worked example · read from top to bottom
sum from index 1 through index 3
= prefix[4] - prefix[1]
= 10 - 2
= 8

Range sum: the total through index 3 is 10. Remove the first element’s total, 2, leaving 4 + 1 + 3 = 8.

For zero-based, inclusive indexes left and right, the formula is:

Worked example · read from top to bottom
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.

Java
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

  1. Am I working with a continuous range?
  2. Can its answer be expressed using a total up to one boundary minus a total up to another?
  3. 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.

Worked example · read from top to bottom
subarraySum = current - earlier

If the subarray must sum to k:

Worked example · read from top to bottom
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.

Two prefix boundaries with totals earlier and current. The values between them sum to current minus earlier; for target K, look for earlier equals current minus K.

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.

Java
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.

Java
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:

Java
long remainder = Math.floorMod(current, k); // k must be positive

Seed 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:

Worked example · read from top to bottom
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):

Worked example · read from top to bottom
answer = prefix[r2 + 1][c2 + 1]
       - prefix[r1][c2 + 1]
       - prefix[r2 + 1][c1]
       + prefix[r1][c1]

A rectangle query in a grid: take the full top-left total, subtract the area above and the area left, then add their overlap back.

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

  1. Mixing conventions. Here, prefix[i] means the first i values. Do not mix it with a tutorial that stores the sum through index i.
  2. Missing the extra zero. It makes ranges beginning at index zero work naturally.
  3. Forgetting the initial map entry. Counting needs (0, 1); longest length needs (0, -1).
  4. Using a set for counting. Repeated prefix totals must retain their frequencies.
  5. Replacing earliest indexes. For longest length, use putIfAbsent.
  6. Recording before checking. That can count an empty range when the target is zero.
  7. Overflowing totals or answers. Use long for prefix totals and potentially large counts. Check the actual constraints; long is larger, not unlimited.
  8. Using an unnormalized negative remainder. Use Math.floorMod with a positive divisor.
  9. 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.

  1. Build the prefix array for [3, -2, 5, 1]. Answer: [0, 3, 1, 6, 7].
  2. Find the sum of indexes 1..3. Answer: 7 - 3 = 4.
  3. Solve Range Sum Query — Immutable.
  4. Solve Find Pivot Index: compare the sum before an index with the sum after it.
  5. Work through Subarray Sum Equals K in Java, then try the linked LeetCode problem yourself.
  6. Revisit Longest Subarray with Sum K.
  7. Try Contiguous Array for the zero-to-minus-one transformation.
  8. Try Subarray Sums Divisible by K.
  9. 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 Sum

Count subarrays with sum K using a prefix sum and frequency map, with beginner-friendly diagrams, a dry run, Java solutions, and common mistakes.

Back to Arrays →