Prefix Sum Algorithm Explained

Prefix sum is an algorithm pattern that preprocesses cumulative totals so range queries can be answered quickly.

It is useful when code repeatedly asks questions such as “what is the sum from index l to index r?” or “how many events happened before this point?”

Quick answer

A prefix sum array stores cumulative totals from the start of the input.

For an input:

nums = [3, 1, 4, 2]

A common prefix shape is:

prefix = [0, 3, 4, 8, 10]

Then the sum from index left through right is:

prefix[right + 1] - prefix[left]

Building the prefix array is O(n). Each range sum query becomes O(1).

Why prefix sums help

Without prefix sums, each range query may scan the range.

If there are many queries, that repeated work adds up:

q queries * up to n values per query = O(q * n)

With prefix sums:

build once: O(n)
each query: O(1)
total: O(n + q)

This is the main tradeoff: spend extra memory and preprocessing time to make repeated queries cheap.

Read Big-O Notation Explained for the growth model behind this kind of preprocessing.

Java prefix sum example

public final class RangeSum {
    private final int[] prefix;

    public RangeSum(int[] nums) {
        this.prefix = new int[nums.length + 1];

        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (left < 0 || right >= prefix.length - 1 || left > right) {
            throw new IllegalArgumentException("invalid range");
        }

        return prefix[right + 1] - prefix[left];
    }
}

Example:

RangeSum sums = new RangeSum(new int[] {3, 1, 4, 2});

System.out.println(sums.sumRange(1, 3)); // 1 + 4 + 2 = 7

The extra leading zero makes boundaries easier because sumRange(0, right) works without a special case.

Prefix sum with counts

Prefix arrays do not have to store numeric sums only. They can also store counts.

Example: count how many values are even up to each index.

int[] evenPrefix = new int[nums.length + 1];

for (int i = 0; i < nums.length; i++) {
    evenPrefix[i + 1] = evenPrefix[i] + (nums[i] % 2 == 0 ? 1 : 0);
}

Now the number of even values in a range is:

int count = evenPrefix[right + 1] - evenPrefix[left];

This same idea works for flags, categories, status codes, and other cumulative counts.

Prefix sums and subarray sums

Prefix sums can solve subarray sum problems by comparing cumulative totals.

If:

prefix[j] - prefix[i] = target

Then the subarray from i to j - 1 sums to target.

For counting subarrays with a target sum, use a hash map of prefix frequencies:

public static int countSubarraysWithSum(int[] nums, int target) {
    Map<Integer, Integer> counts = new HashMap<>();
    counts.put(0, 1);

    int prefix = 0;
    int total = 0;

    for (int value : nums) {
        prefix += value;
        total += counts.getOrDefault(prefix - target, 0);
        counts.merge(prefix, 1, Integer::sum);
    }

    return total;
}

This works even when numbers can be negative, which is one reason prefix sums are useful when a simple sliding window is not valid.

Read Sliding Window Algorithm Explained for the contiguous-window pattern and its limitations with negative numbers.

Difference arrays

A difference array is a related trick for applying many range updates efficiently.

Suppose you need to add 5 to every value from index 2 to index 6. Instead of updating every element immediately, mark the boundaries:

diff[2] += 5
diff[7] -= 5

After all updates, take a prefix sum over diff to recover the final values.

This turns many range updates from repeated O(n) work into boundary updates plus one final scan.

Prefix sums vs sliding window

Both patterns deal with contiguous ranges, but they solve different problems.

Pattern	Best for
Prefix sum	Many range queries, target subarray sums, immutable arrays
Sliding window	One-pass longest or shortest valid window with movable state
Two pointers	Pair search, sorted scans, merging, partitioning

Prefix sums are often better when there are many queries or negative values. Sliding window is often better when you only need one pass and the validity condition behaves predictably as the window grows or shrinks.

Backend-style examples

Prefix sums show up in backend and data-adjacent work:

• Counting events before a timestamp bucket.
• Summing daily usage over date ranges.
• Building cumulative dashboards.
• Answering many range queries over an immutable array.
• Computing rolling reports after preprocessing.
• Applying batch range adjustments with a difference array.

In databases, indexes and precomputed aggregates can play a similar role: do work once so repeated queries do not scan everything.

Complexity

Operation	Complexity
Build prefix array	O(n)
Range sum query	O(1)
Count target subarrays with hash map	O(n) average
Extra space	O(n)

The extra memory is the cost of fast repeated queries.

Use long instead of int when cumulative totals can overflow:

long[] prefix = new long[nums.length + 1];

Common mistakes

The first mistake is off-by-one errors. The leading zero prefix shape usually makes queries easier, but only if you consistently use prefix[right + 1] - prefix[left].

The second mistake is forgetting overflow. Many small values can add up to a large cumulative total.

The third mistake is using prefix sums when the data changes frequently. If every update requires rebuilding the prefix array, another structure may be better.

The fourth mistake is assuming prefix sums only work for sums. Counts and cumulative category totals are often just as useful.

The fifth mistake is missing the hash-map version for target subarray sums, especially when negative numbers make sliding window invalid.

Practical recommendation

Use prefix sums when you see repeated range queries or subarray sums.

Ask:

1. Is the input mostly static?
2. Will there be many range queries?
3. Can cumulative totals answer each query cheaply?
4. Could values overflow an int?

If yes, prefix sums are often one of the simplest optimizations available.

Related reading

Read Sliding Window Algorithm Explained for moving contiguous ranges and Two Pointers Algorithm Explained for broader pointer-based scans.

For complexity and Java collection support, read Big-O Notation Explained, Time Complexity of Java Collections, and use the Big-O Cheat Sheet. For the full sequence, browse the Algorithms and Complexity Learning Path and the Topics map.