정수 n개로 된 수열 a_1, a_2, …, a_n과 질문 q개가 주어진다.
각 질문은 두 수 l, r로 이루어지며, a_l부터 a_r까지(양 끝 포함)의 합을 묻는다.
질문마다 답을 한 줄씩, 질문이 주어진 차례대로 출력하라.
첫 줄에 n과 q, 둘째 줄에 a_1 … a_n, 그다음 q줄에 l과 r이 빈칸으로 나뉘어 주어진다.
5 3 3 -1 4 1 -5 1 3 2 5 4 4
6 -1 1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
질문마다 l부터 r까지 다시 더하면 최대 10^4 × 2×10^4 = 2×10^8번 더하게 되어 Python은 시간 안에 끝나지 않아요(C·C++는 아직 버티지만 n, q가 더 커지면 마찬가지예요).
크레이콘은 실행 걸음이 약 5천만 번을 넘으면 ‘너무 오래 걸려서’로 멈춰서, 이 방법은 기계 속도와 상관없이 늘 시간 초과예요.
누적 합 P[i] = a_1 + … + a_i(P[0] = 0)를 한 번 만들어 두면 답은 P[r] - P[l-1]로 바로 나와요.
흔한 실수는 P[r] - P[l]로 빼서 a_l을 빠뜨리는 것, 그리고 합이 최대 10^13이라 C·C++·Java·C#에서 int(약 21억)에 담는 것이에요 — long/long long을 써요.
Python은 정수 크기에 끝이 없고, JavaScript·TypeScript·크레이콘은 2^53까지 정확해서 괜찮아요.
입력이 많아서 Python은 sys.stdin, Java는 BufferedReader, C++는 sync_with_stdio(false)로 빨리 읽어요.
크레이콘은 목록에 10,000개까지만 넣을 수 있어서 n + 1칸짜리 P 대신 a[i] = a[i] + a[i - 1]로 a를 그 자리에서 누적 합으로 바꾸고, 질문은 콘솔.수들읽기()로 한 줄씩 읽어요.
import sys data = sys.stdin.buffer.read().split()n, q = int(data[0]), int(data[1])prefix = [0] * (n + 1) # prefix[i] = 앞에서 i개의 합for i in range(n): prefix[i + 1] = prefix[i] + int(data[2 + i])out = []pos = 2 + nfor _ 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)))const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = t;const prefix = new Array(n + 1).fill(0); // prefix[i] = 앞에서 i개의 합for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + t[2 + i];const out = [];for (let k = 0, pos = 2 + n; k < q; k++, pos += 2) { const l = t[pos], r = t[pos + 1]; out.push(prefix[r] - prefix[l - 1]);}console.log(out.join("\n"));import { readFileSync } from "node:fs";const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = t;const prefix: number[] = new Array(n + 1).fill(0); // prefix[i] = 앞에서 i개의 합for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + t[2 + i];const out: number[] = [];for (let k = 0, pos = 2 + n; k < q; k++, pos += 2) { const l = t[pos], r = t[pos + 1]; out.push(prefix[r] - prefix[l - 1]);}console.log(out.join("\n"));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken()); long[] prefix = new long[n + 1]; // prefix[i] = 앞에서 i개의 합 st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); int l = Integer.parseInt(st.nextToken()), r = Integer.parseInt(st.nextToken()); out.append(prefix[r] - prefix[l - 1]).append('\n'); } System.out.print(out); }}using System;using System.IO;using System.Text; class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]), q = int.Parse(t[1]); long[] prefix = new long[n + 1]; // prefix[i] = 앞에서 i개의 합 for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + long.Parse(t[2 + i]); var sb = new StringBuilder(); for (int k = 0, pos = 2 + n; k < q; k++, pos += 2) { int l = int.Parse(t[pos]), r = int.Parse(t[pos + 1]); sb.Append(prefix[r] - prefix[l - 1]).Append('\n'); } Console.Write(sb); }}#include <iostream>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<long long> prefix(n + 1, 0); // prefix[i] = 앞에서 i개의 합 for (int i = 0; i < n; i++) { long long x; std::cin >> x; prefix[i + 1] = prefix[i] + x; } for (int k = 0; k < q; k++) { int l, r; std::cin >> l >> r; std::cout << prefix[r] - prefix[l - 1] << '\n'; }}#include <stdio.h>#include <stdlib.h> int main(void) { int n, q; scanf("%d %d", &n, &q); long long *prefix = malloc((n + 1) * sizeof *prefix); // prefix[i] = 앞에서 i개의 합 prefix[0] = 0; for (int i = 0; i < n; i++) { long long x; scanf("%lld", &x); prefix[i + 1] = prefix[i] + x; } for (int k = 0; k < q; k++) { int l, r; scanf("%d %d", &l, &r); printf("%lld\n", prefix[r] - prefix[l - 1]); } free(prefix); return 0;}첫줄 = 콘솔.수들읽기();n = 첫줄[0];q = 첫줄[1];// a를 그 자리에서 누적 합으로 바꾼다: a[i] = 앞에서 i+1개의 합a = 콘솔.수들읽기();반복 (i = 1; i < n; i++){ a[i] = a[i] + a[i - 1];}반복 (k = 0; k < q; k++){ lr = 콘솔.수들읽기(); l = lr[0]; r = lr[1]; 만약 (l == 1) { 콘솔.쓰기(a[r - 1]); } 아니면 { 콘솔.쓰기(a[r - 1] - a[l - 2]); }}