Prefix sums: range query

Precompute running totals once, then answer any "sum from l to r" question with a single subtraction.

Time O(n) build, O(1) querySpace O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

pre[i] holds the sum of the first i elements. The sum of a[l..r] is everything up to r minus everything before l.

Code

C++PythonC#

vector<int> buildPrefix(const vector<int>& a) {
    vector<int> pre(a.size() + 1, 0);
    for (int i = 0; i < (int)a.size(); i++)
        pre[i + 1] = pre[i] + a[i];
    return pre;
}

int rangeSum(const vector<int>& pre, int l, int r) {
    return pre[r + 1] - pre[l];
}

def build_prefix(a: list[int]) -> list[int]:
    pre = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        pre[i + 1] = pre[i] + x
    return pre

def range_sum(pre: list[int], l: int, r: int) -> int:
    return pre[r + 1] - pre[l]

public static int[] BuildPrefix(int[] a) {
    var pre = new int[a.Length + 1];
    for (int i = 0; i < a.Length; i++)
        pre[i + 1] = pre[i] + a[i];
    return pre;
}

public static int RangeSum(int[] pre, int l, int r) {
    return pre[r + 1] - pre[l];
}

Tips

Making pre one longer than a, with pre[0] = 0, removes every special case at the left edge.
Combine with a Dictionary to count subarrays with a given sum. See the Hashing section.

In the .NET library

There is no cumulative-sum method in LINQ. Aggregate can do it, but the plain loop is clearer and faster.