Prefix sum | One Hint Away

One Hint Away (@onehintaway). Clue: many questions that ask "what is the sum from index left to right?" on an array that never changes.

Worked example: range sum query. Build the prefix array once, then answer every query with one subtraction. This is exactly LeetCode 303, Range Sum Query - Immutable (Easy).

The idea

prefix[i] is the sum of the first i numbers, so prefix[0] = 0. The sum from left to right (both included) is everything up to right, minus everything before left:

sum(left, right) = prefix[right + 1] - prefix[left]

The walk

nums = [3, 1, 4, 1, 5]

i	nums[i]	prefix[i + 1] = prefix[i] + nums[i]
0	3	0 + 3 = 3
1	1	3 + 1 = 4
2	4	4 + 4 = 8
3	1	8 + 1 = 9
4	5	9 + 5 = 14

prefix = [0, 3, 4, 8, 9, 14]. Query sum(1, 3) = prefix[4] - prefix[1] = 9 - 3 = 6 (1 + 4 + 1).

Pseudocode

Pseudocode · any language

function buildPrefix(nums):
    n = length(nums)
    prefix = array of n + 1 zeros
    for i from 0 to n - 1:
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

function rangeSum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

The trap: forgetting the shift. prefix[right] - prefix[left] on the example gives 8 - 3 = 5, which drops nums[3]. Use prefix[right + 1].

Code

class Prefix {
    // build: O(n) time, O(n) space
    static long[] buildPrefix(int[] nums) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        return prefix;
    }

    // query: O(1)
    static long rangeSum(long[] prefix, int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

# build: O(n) time, O(n) space
def build_prefix(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

# query: O(1)
def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

#include <vector>
using namespace std;

// build: O(n) time, O(n) space
vector<long long> buildPrefix(const vector<int>& nums) {
    int n = nums.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

// query: O(1)
long long rangeSum(const vector<long long>& prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];
}

// build: O(n) time, O(n) space
function buildPrefix(nums) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

// query: O(1)
function rangeSum(prefix, left, right) {
    return prefix[right + 1] - prefix[left];
}

Complexity

Version	Build	Each query	Extra space
Add the numbers up per query	none	O(n)	O(1)
Prefix array	O(n)	O(1)	O(n)

With q queries that is O(n · q) against O(n + q). Build before the first question, never once per question.

How it was tested

All four languages answer sum(1, 3) = 6 on the example. They were run on 3,001 inputs (3,000 random arrays of length 1 to 12 with values up to ±100,000, each with 1 to 5 random queries, plus the example) and every answer matched adding the numbers up directly.