Introduction to Prefix Sums

EditorialUpdated Oct 25, 2026

The same numbers, added again and again

Your bank app lists how your balance changed each day: [3, -1, 4, 1, -5, 9], day 0 to day 5. How much did it change from day 2 to day 5? Add them up: 4 + 1 − 5 + 9 = 9. Now from day 1 to day 4: −1 + 4 + 1 − 5, and you added three of those a moment ago. Every question re-adds the days it shares with the one before.

This is the version most people write first:

def sum_range(nums, left, right):
    total = 0
    for i in range(left, right + 1):            # walks the whole range on every call
        total += nums[i]
    return total

Each call walks its whole range. With 10,000 days and 10,000 random questions it added 33,577,196 numbers. Range Sum Query - Immutable allows that many values and calls, and if every question asked about the whole array it would be 100,000,000.

Your bank never does this. It keeps your balance, the running total after each day. The change from day 2 to day 5 is the balance after day 5 minus the balance before day 2: 11 − 2 = 9. One subtraction, however long the range.

Six daily changes, 3, -1, 4, 1, -5, 9, in a row of cells. The running totals 0, 3, 2, 6, 7, 2, 11 sit on the seven fences between and around the cells, labelled P[0] to P[6]. Cells 2 to 5 are shaded. A green bar spans fences 0 to 6 (P[6] = 11), an amber bar spans fences 0 to 2 (P[2] = 2) and is in both totals, so it cancels; the blue bar left over spans fences 2 to 6: nums[2..5] = 11 − 2 = 9. Bottom line: the sum of nums[l..r] is P[r + 1] − P[l].

Running totals, with a zero in front

Call the running totals P. P[0] = 0 is the balance before any day, and each next total adds one value: P[i + 1] = P[i] + nums[i]. So P[i] is the sum of the first i values, and n values have n + 1 totals. For our days, P = [0, 3, 2, 6, 7, 2, 11].

The picture that makes the indexes easy: a total doesn't belong to a value, it stands on the fence between two values. P[i] is the fence just before nums[i]; P[0] is the fence before everything and P[n] the fence after everything. The sum of nums[l..r] is the fence after r minus the fence before l:

sum of nums[l..r] = P[r + 1] − P[l]

Why it's exact: P[r + 1] is nums[0] + … + nums[r], and P[l] is nums[0] + … + nums[l − 1]. Every value before l is in both, so it cancels, and what's left is nums[l] + … + nums[r]. Nothing in that argument cares about signs, so negative values are fine.

The zero in front is what lets a range start at index 0 with no special case: nums[0..2] is P[3] − P[0] = 6 − 0 = 6. Step through the build, then three questions:

Running totals of [3, -1, 4, 1, -5, 9] — The top row is the values. Each running total in the row below sits under the gap before its value: P[i] is the sum of everything to its left.

Now pick the ranges yourself. Below, the same totals are drawn as a walk: one dot per fence, at the height of its total, and each value is the step from one dot to the next. Click any two fences. The values between them add up to how far the walk rose (or fell) between the two dots: the same subtraction, as a picture.

Prefix Pairs: pick any two fences and see the sum of the values between them

The template

Build the totals once, then answer each question with one subtraction. This is Range Sum Query - Immutable, where the questions arrive as calls to sumRange:

class NumArray {
    vector<long long> prefix;                       // prefix[i] = sum of the first i values
public:
    NumArray(vector<int>& nums) : prefix(nums.size() + 1, 0) {
        for (size_t i = 0; i < nums.size(); i++)
            prefix[i + 1] = prefix[i] + nums[i];
    }

    long long sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];    // the fence after right minus the fence before left
    }
};

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)      # prefix[i] = sum of the first i values
        for i, x in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + x

    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]   # fence after right minus fence before left

static class NumArray {
    private final long[] prefix;                    // prefix[i] = sum of the first i values

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

    long sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];    // the fence after right minus the fence before left
    }
}

class NumArray {
    constructor(nums) {
        this.prefix = new Array(nums.length + 1).fill(0);    // prefix[i] = sum of the first i values
        for (let i = 0; i < nums.length; i++)
            this.prefix[i + 1] = this.prefix[i] + nums[i];
    }

    sumRange(left, right) {
        return this.prefix[right + 1] - this.prefix[left];   // the fence after right minus the fence before left
    }
}

Each prints 9, 6, 1 and 11 for nums[2..5], nums[0..2], nums[3..3] and nums[0..5]. Building is O(n) time and O(n) space; each question is O(1), so q questions cost O(n + q) instead of O(n · q).

Two details worth copying. In C++ and Java the totals are long long and long: n values can add up to more than an int holds (the second mistake below shows by how much). And Python has the build in its library: list(accumulate(nums, initial=0)) from itertools gives [0, 3, 2, 6, 7, 2, 11] for our days.

Everything left of i, everything right of i

Some problems ask about the two sides of every index. The left side of i is P[i]; the right side is the total minus the left side minus nums[i] itself.

Find Pivot Index: the first index where the sum to its left equals the sum to its right. You don't even need the whole P, just the total and a running left sum:

def pivot_index(nums):
    total = sum(nums)
    left = 0                                     # sum of everything left of i
    for i, x in enumerate(nums):
        if left == total - left - x:             # the right side: what's left after the left side and x
            return i
        left += x
    return -1

It prints 3, -1 and 0 for [1, 7, 3, 6, 5, 6], [1, 2, 3] and [2, 1, -1]. In the last one the pivot is index 0: nothing is to its left, so its left sum is 0, and 1 + (−1) is 0 too. O(n) time, O(1) space.

Product of Array Except Self asks, at every i, for the product of everything except nums[i], without division. It's the same split with products: everything left of i times everything right of i. The first pass writes the left products into the answer. The second walks back from the right with one running product and multiplies it in.

Product of Array Except Self on [2, 3, 0, 4] — The shaded values are the side being multiplied: the left side on the first pass, the right side on the second.

vector<int> productExceptSelf(const vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);
    for (int i = 1; i < n; i++)
        answer[i] = answer[i - 1] * nums[i - 1];    // product of everything left of i
    int right = 1;                                  // product of everything right of i
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= right;
        right *= nums[i];
    }
    return answer;
}

def product_except_self(nums):
    n = len(nums)
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]  # product of everything left of i
    right = 1                                    # product of everything right of i
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

static int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    answer[0] = 1;
    for (int i = 1; i < n; i++)
        answer[i] = answer[i - 1] * nums[i - 1];    // product of everything left of i
    int right = 1;                                  // product of everything right of i
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= right;
        right *= nums[i];
    }
    return answer;
}

function productExceptSelf(nums) {
    const n = nums.length;
    const answer = new Array(n).fill(1);
    for (let i = 1; i < n; i++)
        answer[i] = answer[i - 1] * nums[i - 1];    // product of everything left of i
    let right = 1;                                  // product of everything right of i
    for (let i = n - 1; i >= 0; i--) {
        answer[i] *= right;
        right *= nums[i];
    }
    return answer;
}

Each prints 0 0 24 0, 24 12 8 6 and 0 0 9 0 0 for [2, 3, 0, 4], [1, 2, 3, 4] and [-1, 1, 0, -3, 3]. Two passes, O(n) time, and no extra array beyond the answer. There's no case for zeros, because nothing is ever divided.

Which operations work

Running totals work for any operation you can undo. For sums the undo is subtraction. XOR undoes itself (x ^ x = 0), so running XORs answer range XORs: P[r + 1] ^ P[l]. XOR Queries of a Subarray:

def xor_queries(arr, queries):
    prefix = [0] * (len(arr) + 1)               # prefix[i] = XOR of the first i values
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] ^ x
    return [prefix[r + 1] ^ prefix[l] for l, r in queries]   # XOR undoes itself

For arr = [1, 3, 4, 8] it prints [2, 7, 14, 8] for the ranges [0, 1], [1, 2], [0, 3] and [3, 3].

Products undo with division, which works until a value is 0 (the last mistake below). Maximum and minimum can't be undone at all. For [5, 1, 3], the running maximum up to index 0 is 5 and up to index 2 is 5, yet the largest of nums[1..2] is 3: no subtraction gets 3 out of two fives. Range maximums need a sparse table or a segment tree, in the Advanced section.

Spotting it

Reach for running totals when you see:

many questions about the sum of a range of an array that doesn't change ("sumRange", "queries [l, r]");
the sum or product of everything left or right of each index ("pivot", "balance point", "except itself");
a range of XORs, or of any operation you can undo.

And watch for the near-misses:

the values change between questions (Range Sum Query - Mutable): one change moves every later total, so each update costs O(n). That's a Fenwick tree, in the Advanced section.
the largest or smallest value in a range: nothing to subtract (above).
a subarray whose sum is k, to count them or find the longest: running totals plus a hash map, the next lesson, Prefix Sums with a Hash Map.
all values positive, and the shortest or longest stretch under a limit: a sliding window does it in O(1) space (Variable-Size Sliding Window: Longest and Shortest).

Common mistakes

No zero in front. prefix[i] holds nums[0] + … + nums[i], and a range is prefix[right] - prefix[left - 1]

Every range that starts after 0 works. Then sumRange(0, 2) on [3, -1, 4, 1, -5, 9] asks for prefix[-1], and the same bug fails differently in each language. Python returns -5 instead of 6: prefix[-1] quietly reads the last total, 11. Java stops with ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 6. JavaScript returns NaN, since prefix[-1] is undefined. C++ reads memory before the vector, which is undefined behaviour: it can print anything. Put the zero in front and the case disappears.

Totals in an int. int[] prefix = new int[n + 1]

100,000 values of 100,000 add up to 10^10. Java's int tops out near 2.1 · 10^9 and wraps around silently: the last total printed 1410065408, while the same loop with long printed 10000000000. Keep totals in long long or long whenever n times the largest value can pass 2^31 − 1 (JavaScript numbers are exact up to 2^53, and Python's never overflow).

Counting nums[i] on its own side. if left == total - left

In Find Pivot Index the pivot belongs to neither side. This version leaves it on the right, and on [1, 7, 3, 6, 5, 6] it returns -1 instead of 3. Subtract nums[i] too.

Dividing the total product. total // x

It works for [1, 2, 3, 4], giving [24, 12, 8, 6]. On [2, 3, 0, 4] it crashes: ZeroDivisionError: integer division or modulo by zero. Patching it means counting zeros (one zero: only its own index gets a product; two: every answer is 0), and the problem forbids division anyway. Left and right products never divide.

Check yourself

Quiz

1 / 6

Multiple choice

P = [0, 3, 2, 6, 7, 2, 11] for nums = [3, -1, 4, 1, -5, 9]. Which gives the sum of nums[1..4]?

Practice problems

From easier to harder:

Range Sum Query - Immutable: the template, as a class.
Find Pivot Index: a total and a running left sum.
Product of Array Except Self: left products, then right products, no division.
XOR Queries of a Subarray: running XORs.

Next, Prefix Sums with a Hash Map turns the subtraction around: instead of asking for the sum between two fences, it asks which earlier fence makes the sum come out to k.