Lv.3fenwick-treesegment-tree
값이 바뀌는 구간 합
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
정수 배열 values와 명령 배열 ops가 주어집니다. 명령은 순서대로 처리하며, 두 종류가 있습니다.
[1, i, x]:values[i]를x로 바꿉니다.[2, l, r]:values[l] + values[l+1] + … + values[r]를 구합니다.
2번 명령의 답을 나온 순서대로 배열에 담아 반환하세요.
입출력 예
| values | ops | result |
|---|---|---|
[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[]
제한 사항
-
values.length -
ops.length -
values[i],x [1, i, x]: /[2, l, r]:2번 명령은 적어도 하나 있습니다. 합은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O((N + Q) log N)
- 공간
- O(N)
입출력 예
| values | ops | 기대 출력 |
|---|---|---|
[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] |
힌트
힌트
누적 합 배열은 구간 합을 에 주지만, 값 하나가 바뀌면 뒤쪽을 전부 고쳐야 해서 이 듭니다. **수정과 질의를 모두 **에 하는 자료구조가 필요합니다.
**펜윅 트리(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비트 정수로 관리하세요.
복잡도 목표
질의마다 구간을 직접 더하거나, 수정마다 누적 합을 다시 만드는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 266 ms | 추정 |
| C++ (GCC, gnu++23) | 266 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 2072 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1532 ms | 추정 |
| C# 14 (.NET 10) | 1532 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 8 | 판정만 |
| performance | 60 | 4 | 판정만 |