Back to solutions

Range Sum Query - Immutable

EasyArrays

Answer many subarray-sum queries quickly with prefix sums.

Open problem
Constraints
  • 1 <= n <= 10^4
  • 0 <= i <= j < n
  • 1 <= q <= 10^4

Prefix sums

Time O(n) build, O(1) per querySpace O(n)

Precompute pre[k] = sum of the first k elements. Then the sum of nums[i..j] is pre[j+1] - pre[i], answered in O(1). Building the prefix array is one pass; every query is then instant.

Key terms
prefix sum array:
pre[k] holds the total of the first k elements; pre[0] = 0.
immutable:
The array never changes, so a one-time precomputation is worthwhile.
struct NumArray {
    vector<long long> pre;
    NumArray(vector<int>& nums) {
        pre.assign(nums.size() + 1, 0);
        for (size_t i = 0; i < nums.size(); i++) pre[i + 1] = pre[i] + nums[i];
    }
    long long sumRange(int i, int j) { return pre[j + 1] - pre[i]; }
};
Step by step
  1. Build pre of length n+1 with pre[0] = 0 and pre[i+1] = pre[i] + nums[i].
  2. For a query (i, j), return pre[j+1] - pre[i].
  3. The subtraction cancels everything before i, leaving exactly nums[i..j].