BOJ 11659 — Range Sum Query 4

BOJ 11659: Range Sum Query 4

For an array, build a prefix-sum array where prefix[0] = 0 and prefix[i + 1] = prefix[i] + value[i]. The sum of an inclusive range [a, b] is prefix[b] - prefix[a - 1]. The input positions are 1-indexed, so the prefix indices account for converting them to Java’s 0-indexed array.

The prefix array is built in O(N) time, and each of the M queries is answered in O(1), for O(N + M) total time and O(N) space. A BufferedReader and StringTokenizer read tokens across arbitrary whitespace, and a StringBuilder collects the answers before output.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  private static BufferedReader reader =
      new BufferedReader(new InputStreamReader(System.in));
  private static StringTokenizer tokenizer;

  private static int nextInt() throws IOException {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine());
    }
    return Integer.parseInt(tokenizer.nextToken());
  }

  public static void main(String[] args) throws IOException {
    int n = nextInt();
    int m = nextInt();
    int[] prefix = new int[n + 1];

    for (int i = 0; i < n; i++) {
      prefix[i + 1] = prefix[i] + nextInt();
    }

    StringBuilder output = new StringBuilder();
    for (int i = 0; i < m; i++) {
      int a = nextInt();
      int b = nextInt();
      output.append(prefix[b] - prefix[a - 1]).append('\n');
    }
    System.out.print(output);
  }
}