Challenge: Step Counter Questions

Lab Java Beginner 10 points

A fitness watch logged steps for n days. Answer q questions “total steps from day a to day b” (days numbered from 1, both included). Build prefix sums once, then answer each question in O(1).

Input

Line 1: n q. Line 2: n step counts. Then q lines a b.

Output

One total per question, each on its own line.

Example

Input

7 3
4000 6500 3000 8000 7200 5100 9900
2 5
1 7
6 6

Output

24700
43700
5100

Sample input available Sample output available

Editor

Java

Hints

Days start at 1 here, so pre[i] = total of days 1..i fits nicely.

Total of days a..b is pre[b] - pre[a - 1]. Use long – the totals can be huge.

Solution explanation

O(n) to build the totals, then O(1) per question: O(n + q) overall.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), q = sc.nextInt();
        long[] pre = new long[n + 1];
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < q; k++) {
            int a = sc.nextInt(), b = sc.nextInt();
            sb.append(pre[b] - pre[a - 1]).append('\n');
        }
        System.out.print(sb);
    }
}

Output

Answer