Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Adding up a[l..r] for every query is O(n·q) — up to 10^10 steps.
  2. 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);
    }
}

Solve Range Sum Queries online · All practice problems