Funcia
Lv.3fenwick-treesegment-tree

값이 바뀌는 구간 합

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 values와 명령 배열 ops가 주어집니다. 명령은 순서대로 처리하며, 두 종류가 있습니다.

  • [1, i, x]: values[i]를 x로 바꿉니다.
  • [2, l, r]: values[l] + values[l+1] + … + values[r]를 구합니다.

2번 명령의 답을 나온 순서대로 배열에 담아 반환하세요.

입출력 예

valuesopsresult
[1, 2, 3, 4, 5][[2, 0, 4], [1, 2, 10], [2, 1, 3], [2, 2, 2]][15, 16, 10]
[-5, 5][[1, 0, 7], [1, 0, -1], [2, 0, 1]][4]

입출력 예 설명

예 1 — 처음 전체 합은 15입니다. values[2]를 10으로 바꾸면 배열이 [1, 2, 10, 4, 5]가 되어 [1, 3] 구간 합은 16, [2, 2]는 10입니다.

예 2 — values[0]이 7을 거쳐 -1이 되므로 합은 -1 + 5 = 4입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

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

제한 사항

  • 1≤N=1 \le N = values.length ≤200,000\le 200{,}000
  • 1≤Q=1 \le Q = ops.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le values[i], x ≤109\le 10^9
  • [1, i, x]: 0≤i<N0 \le i < N / [2, l, r]: 0≤l≤r<N0 \le l \le r < N
  • 2번 명령은 적어도 하나 있습니다. 합은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

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

입출력 예

valuesops기대 출력
[1,2,3,4,5][[2,0,4],[1,2,10],[2,1,3],[2,2,2]][15,16,10]
[-5,5][[1,0,7],[1,0,-1],[2,0,1]][4]

힌트

힌트

누적 합 배열은 구간 합을 O(1)O(1)에 주지만, 값 하나가 바뀌면 뒤쪽을 전부 고쳐야 해서 O(N)O(N)이 듭니다. **수정과 질의를 모두 O(log⁡N)O(\log N)**에 하는 자료구조가 필요합니다.

**펜윅 트리(BIT)**가 가장 짧습니다. tree[i]가 i & -i만큼의 구간 합을 맡습니다.

add(i, delta):  i += 1; while i <= N: tree[i] += delta; i += i & -i
prefix(i):      합 of values[0..i-1]; while i > 0: s += tree[i]; i -= i & -i
  • 값 바꾸기 [1, i, x]: 현재 값을 따로 기억해 두고 add(i, x - cur[i]).
  • 구간 합 [2, l, r]: prefix(r + 1) - prefix(l).

세그먼트 트리로 풀어도 됩니다. 어느 쪽이든 합은 64비트 정수로 관리하세요.

복잡도 목표

질의마다 구간을 직접 더하거나, 수정마다 누적 합을 다시 만드는 O(NQ)O(NQ) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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