Funcia
Lv.1arrayprefix-sum

구간 합 질의

메모리 제한
256 MB
정확성 시간 제한
10000 ms
정답률
100.0%
푼 사람
1
0

구간 합 질의

정수 배열 values와 질의 배열 queries가 주어집니다. 각 질의 [l, r]에 대해 values[l] + values[l+1] + ... + values[r] (양 끝 포함, 0부터 시작하는 인덱스)을 계산하여, 질의 순서대로 결과를 담은 배열을 반환하세요.

제한 사항

  • 1≤1 \le values.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le values[i] ≤109\le 10^9
  • 1≤1 \le queries.length ≤200,000\le 200{,}000
  • queries[i] = [l, r], 0≤l≤r<0 \le l \le r < values.length
  • 합은 32비트 정수 범위를 넘을 수 있습니다. 64비트 정수(long)를 사용하세요.

입출력 예

valuesqueriesresult
[1, 2, 3, 4, 5][[0, 4], [1, 3], [2, 2]][15, 9, 3]
[-3, 10, -2][[0, 1], [1, 2], [0, 0]][7, 8, -3]

입출력 예 설명

첫 번째 예: 구간 [0, 4]의 합은 1+2+3+4+5 = 15, [1, 3]은 2+3+4 = 9, [2, 2]는 3입니다.

효율성

예상 시간 복잡도는 O(N+Q)O(N + Q) 입니다. 질의마다 구간을 직접 더하는 O(N×Q)O(N \times Q) 풀이는 효율성 테스트에서 시간 초과가 납니다.

함수 시그니처

solution(values: long[], queries: int[][]) → long[]

기대 복잡도

시간
O(N + Q)
공간
O(N)

입출력 예

valuesqueries기대 출력
[1,2,3,4,5][[0,4],[1,3],[2,2]][15,9,3]
[-3,10,-2][[0,1],[1,2],[0,0]][7,8,-3]

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)246 ms추정
C++ (GCC, gnu++23)246 ms도출됨
Python 3.131000 ms도출됨
Java 252122 ms도출됨
Kotlin 2.4 (JVM)1492 ms추정
C# 14 (.NET 10)1492 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness408판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.