2Brute2Best
🔥0

Prefix Sum Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Store running totals so the sum of any range becomes one subtraction: sum(l..r) = prefix[r+1] − prefix[l].

5 sub-patterns · 18 questions

Remember this · Prefix Sum
Trigger
Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.
Think
If I knew the total up to every index, would the answer become a difference of two totals?
Key question
Which earlier prefix value am I looking for when I stand at index i?
A

What is this pattern?

Prefix Sum means storing running totals so you never add up the same numbers twice.

prefix[i] is the sum of the first i elements, with prefix[0] = 0. Then the sum of any range is one subtraction:

sum(l..r) = prefix[r + 1] − prefix[l]

There are two ways to use it:

  • Answer range queries: build prefix once, then each "sum from l to r" costs O(1).
  • Search for a range: walk left to right keeping the running total. At index i, ask "which earlier total would make the range between us right?" and look it up in a hash map of totals you've already seen.

The second use is the powerful one. It works even with negative numbers, where a sliding window breaks.

Your bank statement shows the balance after every transaction. To know how much you spent between March 3 and March 10, you don't add up every transaction — you subtract the two balances. And if you want to know whether some stretch of days added up to exactly ₹0, you just check whether the same balance ever appeared twice.

B

See it move

prefix has n + 1 cells: prefix[i] sits just before nums[i]. The two blue cells are the only ones a query reads.

Build once, then every range is one subtractionnums = [3, -2, 5, 1, -4, 6], queries = [1, 3], [0, 4], [2, 5]step 1/10
nums
0
1
2
3
4
5
3
-2
5
1
-4
6
prefix
0
1
2
3
4
5
6
0
Build
prefix[0]
0
prefix[0] = 0 (the empty prefix)

prefix has one more cell than nums. prefix[i] is the total of everything before nums[i], so prefix[0] = 0.

Count subarrays with sum exactly 3. Gold prefix cells are the earlier totals that pair with the current one (blue).

Look up prefix − k in the totals seen so farnums = [1, 2, -1, 2, 1, -3, 3], k = 3step 1/9
nums
0
1
2
3
4
5
6
1
2
-1
2
1
-3
3
prefix
0
1
2
3
4
5
6
7
0
total → times seen
0:1
State
k
3
prefix
0
count
0
Seed the map with total 0

Before reading anything, the running total is 0. Putting 0 in the map lets ranges that start at index 0 be found.

C

How do I recognise it?

  • Many range-sum questions on an array that never changes ("sum from l to r", "sum of a rectangle").

  • "Number of subarrays with sum exactly K" — especially when the array can have negative numbers or zeros.

  • "Longest subarray with equal number of 0s and 1s / X and Y" — turn one kind into −1 and look for a zero total.

  • "Sum divisible by K" or "sum is a multiple of K" — compare remainders of totals.

  • "For every index, combine something from its left and its right" (pivot index, product except self).

Looks like Prefix Sum, but isn't

Longest / shortest subarray with sum ≤ K, all numbers positive
→ Sliding Window

With only positives, the window sum grows when you extend and shrinks when you move left, so a window is O(N) with O(1) space. Prefix + hash map also works but is heavier than needed.

Range sum queries while the array is also being **updated**
→ Fenwick tree / segment tree

One update changes every prefix after it — O(N) per update. Trees give O(log N) for both updates and queries.

Two elements (not a range) that add up to K
→ Hash map (Two Sum) or Two Pointers

Prefix sums are about contiguous ranges. A pair of separate elements is a different question.

Maximum subarray sum (no target given)
→ Kadane's algorithm

You can do it with prefix sums (current prefix − smallest earlier prefix), but that is Kadane in disguise. No hash map is needed because there's no exact target to look up.

D

How would I discover it from scratch?

Don't memorise “use prefix sum”. Ask these questions in order — the pattern falls out.

Try every start l and every end r, and add up nums[l..r] — O(N³). Or keep a running sum per start — O(N²).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Static range sum

3 questions

The data never changes, and you're asked for many range sums. Build the prefix array once (O(N)), then answer each question with one subtraction.

02

Exact sum + hash map

5 questions

Find (or count) contiguous ranges whose sum is exactly K. Walk left to right; at each index look up prefix − K in a map of earlier totals.

03

Prefix state / balance

3 questions

Recode each element so that "balanced" becomes "the same state as before": 0 → −1 and 1 → +1, or a bitmask of odd/even counts. Then the longest balanced range runs between the first and the latest time a state appears.

04

Modulo / divisibility

3 questions

A range sum is divisible by K exactly when the totals at its two ends leave the same remainder. Store remainders instead of totals.

05

Prefix + suffix

4 questions

Each index needs something from everything on its left and everything on its right. Make one pass from the left, one from the right, then combine.

F

Don't mix these up

Prefix Sum + hash map vs Sliding Window

All numbers positive and the condition is "at most / at least"? Sliding window. Exact sum, or negatives allowed? Prefix sum + hash map — with negatives, shrinking the window doesn't reliably make the sum smaller.

Count map (how many) vs First-index map (longest)

Counting ranges → count[total]++ every time. Longest range → save the index only the first time, so later matches stretch as far back as possible.

Exact sum (look up prefix − K) vs Divisible by K (look up same remainder)

"Equals K" is a subtraction on the totals. "Divisible by K" ignores everything except the remainder — two totals match when a % k == b % k.

Prefix sum vs Prefix product

Sums can be undone by subtraction. Products can't be safely undone by division (zeros!), so keep the left part and the right part separately and multiply them.

G

Code templates (C++)

Build once, query in O(1)

The array has n + 1 cells. The leading 0 means a range starting at l = 0 needs no special case.

range-template.cpp
// Build once: prefix[i] = sum of the first i elements, prefix[0] = 0.
vector<long long> buildPrefix(const vector<int>& nums) {
    vector<long long> prefix(nums.size() + 1, 0);
    for (int i = 0; i < (int)nums.size(); i++)
        prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

// Sum of nums[l..r] (inclusive) in O(1): everything up to r, minus everything before l.
long long rangeSum(const vector<long long>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

Count ranges with sum exactly K

Look up first, then insert. The map holds totals strictly before the current index, so the range is never empty.

count-template.cpp
// Count subarrays whose sum is exactly k. Works with negatives and zeros.
long long countSubarrays(vector<int>& nums, int k) {
    unordered_map<long long, int> seen;  // prefix total -> how many times it appeared
    seen[0] = 1;                         // the empty prefix, for ranges starting at index 0
    long long prefix = 0, count = 0;
    for (int x : nums) {
        prefix += x;
        auto it = seen.find(prefix - k); // an earlier total that leaves exactly k between us
        if (it != seen.end()) count += it->second;
        seen[prefix]++;                  // insert AFTER the lookup
    }
    return count;
}

Longest range with a balanced state

Store only the first index of each state. Seeing the same state again later means everything in between is balanced.

first-index-template.cpp
// Longest subarray with equal numbers of 0s and 1s.
// Recode 0 -> -1, 1 -> +1: "balanced" now means "same running total as before".
int longestBalanced(vector<int>& nums) {
    unordered_map<int, int> first;  // running total -> FIRST index where it appeared
    first[0] = -1;                  // the empty prefix sits just before index 0
    int balance = 0, best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        balance += nums[i] == 1 ? 1 : -1;
        auto it = first.find(balance);
        if (it != first.end()) best = max(best, i - it->second);
        else first[balance] = i;    // never overwrite: the earliest index gives the longest range
    }
    return best;
}

Divisible by K (remainders)

In C++, -3 % 5 is -3. The + k fix makes every remainder land in 0 … k − 1.

modulo-template.cpp
// Count subarrays whose sum is divisible by k.
// Two totals with the same remainder differ by a multiple of k.
long long countDivisible(vector<int>& nums, int k) {
    vector<long long> count(k, 0);  // remainder -> how many prefixes had it
    count[0] = 1;                   // the empty prefix
    long long prefix = 0, result = 0;
    for (int x : nums) {
        prefix += x;
        int rem = ((prefix % k) + k) % k;  // C++ % can be negative; this keeps it in 0..k-1
        result += count[rem];
        count[rem]++;
    }
    return result;
}

Left pass + right pass

Often the right side doesn't need its own array: it's total − left − nums[i].

left-right-template.cpp
// For every index, combine what's on its left with what's on its right.
// Example: leftSum[i] - rightSum[i], without building a right array.
vector<long long> leftMinusRight(vector<int>& nums) {
    long long total = 0;
    for (int x : nums) total += x;
    vector<long long> answer(nums.size());
    long long left = 0;                         // sum of nums[0..i-1]
    for (int i = 0; i < (int)nums.size(); i++) {
        long long right = total - left - nums[i];  // sum of nums[i+1..n-1]
        answer[i] = left - right;
        left += nums[i];
    }
    return answer;
}
Next
Start with Static range sum