Prefix Sums in C++: O(1) Range-Sum Queries (LeetCode 303)

#cpp #dsa #algorithms #codinginterview

Day 25/75: Prefix Sums for O(1) Range-Sum Queries

75 Day DSA in C++ Challenge

A daily-revenue report I maintain answered every range request with a loop: walk from the left index to the right index, add as you go, return the total. It was correct and it read well, and against a few hundred days of data in development it was fine. Then the data grew to years per tenant, the page started firing dozens of span queries per render, and the request timeout began tripping. The arithmetic was never wrong -- I was just recomputing the same partial sums on every request over data that never changed.

This is LeetCode 303, Range Sum Query - Immutable, and the operative word is immutable.

The naive query and what it costs

#include <vector>

// O(n) per query: re-adds the slice from scratch every time.
long long rangeSumLoop(const std::vector<int>& v, int lo, int hi) {
    long long sum = 0;
    for (int i = lo; i <= hi; ++i) sum += v[i];
    return sum;
}

With q queries over an array of size n, that is O(n * q). In dev, n was small and q was tiny, so nobody noticed. In production both grew, and the product became the whole latency budget.

The prefix-sum array

Define prefix[k] as the sum of the first k elements -- everything strictly before index k. The leading zero (prefix[0] = 0) is what keeps the query branchless.

#include <vector>

class NumArray {
    std::vector<long long> ps;        // ps[k] = sum of the first k elements
public:
    explicit NumArray(const std::vector<int>& v) : ps(v.size() + 1, 0) {
        for (std::size_t i = 0; i < v.size(); ++i)
            ps[i + 1] = ps[i] + v[i]; // running total, single O(n) pass
    }

    long long sumRange(int lo, int hi) const {   // closed [lo, hi]
        return ps[hi + 1] - ps[lo];               // O(1): one subtraction
    }
};

sumRange(lo, hi) returns prefix[hi + 1] - prefix[lo]: everything before hi + 1 minus everything before lo leaves exactly the elements from lo to hi. Build once in O(n), then every query is O(1).

Why the leading zero matters

Size the array to n instead and define prefix[k] as the sum including index k, and the range sum becomes prefix[hi] - prefix[lo - 1]. When lo == 0 that reaches prefix[-1] -- off the front of the array. You end up special-casing the first element on every query. Sizing to n + 1 with a leading zero means prefix[lo] is valid for every lo in [0, n], and sumRange(0, hi) is just prefix[hi + 1] with no branch.

The overflow trap

Use long long, not int, for the prefix array. A prefix sum over a long span of 32-bit values overflows fast -- a few hundred thousand revenue figures clear two billion easily. Stored in int, the totals wrap negative silently, passing every small test and corrupting the number on your biggest tenant.

The mirror trick: difference arrays

Prefix sums give O(1) range queries on static data. The difference array gives O(1) range updates with a single final read. To add v to all of [lo, hi] repeatedly:

#include <vector>

std::vector<long long> applyRangeAdds(
    int n, const std::vector<std::array<int, 3>>& updates) {  // {lo, hi, v}
    std::vector<long long> diff(n + 1, 0);
    for (const auto& u : updates) {
        diff[u[0]]     += u[2];   // add at the start
        diff[u[1] + 1] -= u[2];   // cancel just past the end
    }
    for (int i = 1; i < n; ++i) diff[i] += diff[i - 1];  // prefix sum to recover
    diff.resize(n);
    return diff;
}

Each update is two O(1) writes; one closing O(n) prefix sum reconstructs the array. It is the same running-total machinery read in reverse.

The reflection

The bug was never the loop -- the loop was correct. The waste was recomputing a quantity whose inputs never changed. When the data is immutable and overlapping ranges are queried repeatedly, materialize the partial sums once: trade O(n) of setup and O(n) of memory for O(1) per query. On a reporting endpoint getting hammered with span queries, that trade is the difference between an instant render and a tripped timeout. Tomorrow continues the array-math thread, but the habit carries: before optimizing a loop, ask whether it should run at all.

DEV Community