DSA sheet / Range queries
Static Range Sum Queries
Do these first: Maximum Subarray Sum
The problem in brief
You get an array of n integers (up to 200 000) and q queries (up to 200 000). Each query gives two positions a and b (1-indexed, inclusive); print the sum of the array values from a to b. The array never changes between queries.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1646.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Summing each range from scratch is O(n) per query. What work could you do once, before any query, to make each query cheap?
-
Precompute, for every position i, the sum of the first i elements. How would the sum of a range relate to two such numbers?
-
Think of it as subtracting a shorter prefix from a longer one. Which two prefixes bound the range [a, b], and what is the boundary case for a = 1?
-
The individual values reach 10^9 and there are 200 000 of them. Choose the integer type accordingly.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
When many queries hit the same unchanging data, spend the effort once up front. The two costs are preprocessing and per-query time; brute force is O(1) preprocessing and O(n) per query, for a total of 4 * 10^10 at the limits. Prefix sums give O(n) preprocessing and O(1) per query.
The idea: let P[i] be the sum of the first i elements, with P[0] = 0. Then sum(a..b) = P[b] - P[a - 1]. The leading zero is the trick that removes the special case for ranges starting at position 1. This shape (build a summary once, answer each query by combining two lookups) is the seed of a whole family: 2D prefix sums, difference arrays, and even the Fenwick tree in the next problem, which handles updates too.
Intuition
A running odometer: reading it at position b and at position a - 1 and subtracting tells you the distance travelled between them, without re-driving the route.
Approach
- Read the array and build P with P[0] = 0, P[i] = P[i - 1] + x_i.
- For each query (a, b) print P[b] - P[a - 1].
Pitfalls: prefix sums reach 2 * 10^14 so use 64-bit; keep positions 1-indexed and P sized n + 1; print all answers with one buffered write, since there can be 200 000 lines.
Complexity
O(n + q) time, O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
prefix[i] = prefix[i - 1] + x;
}
string out;
while (q--) {
int a, b;
cin >> a >> b;
out += to_string(prefix[b] - prefix[a - 1]);
out += '\n';
}
cout << out;
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + int(data[1 + i])
out = []
base = 2 + n
for i in range(q):
a = int(data[base + 2 * i])
b = int(data[base + 2 * i + 1])
out.append(prefix[b] - prefix[a - 1])
print("\n".join(map(str, out)))
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int q = (int) st.nval;
long[] prefix = new long[n + 1];
for (int i = 1; i <= n; i++) {
st.nextToken();
prefix[i] = prefix[i - 1] + (long) st.nval;
}
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
st.nextToken();
int a = (int) st.nval;
st.nextToken();
int b = (int) st.nval;
sb.append(prefix[b] - prefix[a - 1]).append('\n');
}
System.out.print(sb);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const q = data[1];
const prefix = new Float64Array(n + 1); // sums stay below 2e14, exact in a double
for (let i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + data[1 + i];
const out = [];
const base = 2 + n;
for (let i = 0; i < q; i++) {
const a = data[base + 2 * i];
const b = data[base + 2 * i + 1];
out.push(prefix[b] - prefix[a - 1]);
}
console.log(out.join('\n'));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).