Practice › Arrays
Range Sum Queries
Easy · Arrays · Asked at Amazon, Google, TCS, Infosys
Answer q queries. Each query l r (1-indexed, inclusive) asks for a[l] + … + a[r].
Input
Line 1: n. Line 2: n integers. Line 3: q. Next q lines: l r.
Output
One sum per query, each on its own line.
Constraints
- 1 ≤ n, q ≤ 10^5
- |a[i]| ≤ 10^9
Build a prefix-sum array once; each query is then O(1). Sums can exceed 32-bit range.
Example 1
Input
5 1 2 3 4 5 3 1 3 2 5 4 4
Output
6 14 4
Example 2
Input
2 -1 1 1 1 2
Output
0
Hints
- Adding up a[l..r] for every query is O(n·q) — up to 10^10 steps.
- Precompute prefix[i] = a[1] + … + a[i]. Then sum(l..r) = prefix[r] − prefix[l − 1].
Approach
Build a prefix-sum array once, with prefix[0] = 0 and prefix[i] = prefix[i-1] + a[i]. Every query is then a single subtraction. Sums can reach 10^14, so use 64-bit integers. With up to 10^5 output lines, collect the output and print it at once.
Complexity: O(n + q) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n;
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;
}
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << prefix[r] - prefix[l - 1] << "\n";
}
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
n = int(data[0])
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + int(data[i])
q = int(data[n + 1])
out = []
pos = n + 2
for _ in range(q):
l, r = int(data[pos]), int(data[pos + 1])
pos += 2
out.append(prefix[r] - prefix[l - 1])
print("\n".join(map(str, out)))Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
long[] prefix = new long[n + 1];
for (int i = 1; i <= n; i++) {
in.nextToken();
prefix[i] = prefix[i - 1] + (long) in.nval;
}
in.nextToken();
int q = (int) in.nval;
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
in.nextToken();
int l = (int) in.nval;
in.nextToken();
int r = (int) in.nval;
sb.append(prefix[r] - prefix[l - 1]).append('\n');
}
System.out.print(sb);
}
}