#067 · 누적합쉬움누적합 (Prefix Sum)

구간 합 쿼리

문제

정수 배열 arr 과 쿼리 배열 queries 가 주어집니다. 각 쿼리는 [l, r] (0-indexed, l ≤ r) 형태이며, arr[l..r] (양 끝 포함) 의 합을 의미합니다. 모든 쿼리에 대한 구간 합을 입력 순서대로 담은 배열을 반환하세요.

예시

arr=[1,2,3,4,5], queries=[[0,2],[1,3],[0,4]]
  → [6, 9, 15]
    [0,2] = 1+2+3 = 6
    [1,3] = 2+3+4 = 9
    [0,4] = 1+2+3+4+5 = 15
 
arr=[10,-5,3], queries=[[0,0],[1,2],[0,2]]
  → [10, -2, 8]

제약 조건

1 ≤ arr.length ≤ 100,000
1 ≤ queries.length ≤ 100,000
-10,000 ≤ arr[i] ≤ 10,000
0 ≤ l ≤ r ≤ arr.length - 1

시간 복잡도 목표: O(N + Q)

테스트 케이스

예시 1: 표준 케이스

입력: arr = [1,2,3,4,5], queries = [[0,2],[1,3],[0,4]]

출력: [6,9,15]

예시 2: 음수 + 단일 인덱스 쿼리

입력: arr = [10,-5,3], queries = [[0,0],[1,2],[0,2]]

출력: [10,-2,8]

예시 3: 원소 1개

입력: arr = [7], queries = [[0,0]]

출력: [7]

예시 4: 모두 1인 배열

입력: arr = [1,1,1,1,1], queries = [[0,4],[1,3],[2,2]]

출력: [5,3,1]

예시 5: 다중 쿼리

입력: arr = [2,4,6,8,10,12], queries = [[2,5],[0,0],[3,4],[0,5]]

출력: [36,2,18,42]

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.