static-range-sum-queries

Static Range Sum Queries

CSES medium

You are given an array of \(n\) integers and \(q\) queries. Each query asks for the sum of values in the inclusive range \([a,b]\). Print the answer for every query.

Solution

Precompute prefix sums so any range sum can be answered in \(O(1)\) time.

Let \(S[0]=0\) and for \(i\ge1\), \(S[i]=S[i-1]+x_i\).

Then for a query \([a,b]\) (1-indexed), the sum is: [ (a,b)=S[b]-S[a-1].]

Building \(S\) is \(O(n)\); answering all queries is \(O(q)\).

Prefix sums (1-indexed)

Build once: \(S[i] = S[i-1] + x_i\) for \(i = 1..n\)
Query: \(S[b] - S[a-1]\)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    vector<long long> pref(n + 1, 0); // pref[0] = 0
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref[i] = pref[i - 1] + x;
    }

    while (q--) {
        int a, b;
        cin >> a >> b;          // 1-indexed ranges
        cout << (pref[b] - pref[a - 1]) << '\n';
    }
}

64-bit sums

Values can reach \(2\cdot10^5 \times 10^9 = 2\cdot10^{14}\), so store prefix sums and results in long long.