크기 N인 수열이 주어지고, 두 종류의 명령이 뒤섞여 들어옵니다.
1 b c— b번째 수를 c로 바꾼다2 b c— b번째부터 c번째까지의 합을 출력한다
N은 최대 1,000,000, 명령은 최대 20,000개입니다.
왜 누적 합으로는 안 되는가
구간 합만 묻는 문제라면 누적 합 배열 하나면 끝납니다. prefix[i] = arr[0] + ... + arr[i] 를 미리 만들어 두면 구간 [l, r]의 합은 prefix[r] - prefix[l-1] 로 질의당 O(1) 입니다.
문제는 중간에 원소가 바뀐다는 점입니다. arr[3] 이 바뀌면 prefix[3] 부터 prefix[N-1] 까지 전부 다시 계산해야 합니다. 변경 한 번에 O(N)입니다.
| 방식 | 변경 | 구간 합 | 최악의 경우 |
|---|---|---|---|
| 매번 직접 더하기 | O(1) | O(N) | 20,000 × 1,000,000 = 200억 |
| 누적 합 | O(N) | O(1) | 20,000 × 1,000,000 = 200억 |
| 세그먼트 트리 | O(log N) | O(log N) | 20,000 × 20 = 40만 |
한쪽만 빠른 자료구조로는 반대쪽 연산에서 무너집니다. 양쪽을 모두 O(log N)으로 맞추는 것이 이 문제의 핵심이고, 그 답이 세그먼트 트리입니다.
세그먼트 트리의 구조
아이디어는 단순합니다. 구간을 절반씩 쪼개 내려가는 이진 트리를 만들고, 각 노드에 자기가 담당하는 구간의 합을 미리 저장해 둡니다.
배열이 [5, 8, 4, 3, 7] 일 때 만들어지는 트리입니다. 괄호 안은 담당 구간, 그 아래 숫자가 저장된 합입니다.
node 1
[0..4]
27
/ \
node 2 node 3
[0..2] [3..4]
17 10
/ \ / \
node 4 node 5 node 6 node 7
[0..1] [2..2] [3..3] [4..4]
13 4 3 7
/ \
node 8 node 9
[0..0] [1..1]
5 8
핵심 성질 세 가지입니다.
- 리프 노드는 원본 배열의 원소 하나를 담당합니다.
- 내부 노드는 두 자식이 담당하는 구간의 합입니다.
tree[node] = tree[2*node] + tree[2*node+1]이 항상 성립합니다. - 노드 번호를 1부터 매기면 자식은
2*node,2*node+1로 계산됩니다. 포인터 없이 배열 하나로 트리를 표현할 수 있습니다.
트리 높이는 ⌈log₂N⌉ 이고, N이 1,000,000이면 20 정도입니다. 어떤 연산이든 루트에서 리프까지 스무 칸만 내려가면 끝난다는 뜻입니다.
배열 크기를 왜 4N으로 잡는가
N이 2의 거듭제곱이면 트리 노드 수는 2N - 1 이면 충분합니다. 하지만 N이 어중간한 수(예: 5)면 마지막 레벨이 삐뚤빼뚤해지면서 노드 번호가 2N을 넘어갑니다. 안전하게 다음 2의 거듭제곱까지 올려 잡으면 최악의 경우 4N 이 됩니다. 계산하기 귀찮으니 그냥 new long[4 * n] 으로 잡는 것이 관례입니다.
세 가지 연산
1. 초기화(init) — O(N)
리프까지 재귀로 내려간 뒤, 돌아 나오면서 두 자식의 합을 채웁니다.
private static long init(long[] nn, long[] tree, int node, int start, int end) {
if (start == end) { // 리프에 닿았다
return tree[node] = nn[start];
}
int mid = (start + end) / 2;
return tree[node] = init(nn, tree, node * 2, start, mid) // 왼쪽 절반
+ init(nn, tree, node * 2 + 1, mid + 1, end); // 오른쪽 절반
}
node 1 이 [0..4] 를 담당한다고 알려주며 시작하면, 중간점 2를 기준으로 왼쪽 자식에게 [0..2], 오른쪽 자식에게 [3..4] 를 맡기는 식으로 저절로 트리 전체가 채워집니다. 노드를 한 번씩만 방문하므로 O(N)입니다.
2. 구간 합(sum) — O(log N)
구간 [1, 3]의 합(= 8 + 4 + 3 = 15)을 구하는 과정을 따라가 보겠습니다. 각 노드에서 내 구간과 질의 구간의 관계를 보고 세 갈래로 갈립니다.
| 관계 | 처리 |
|---|---|
| 전혀 안 겹침 | 0을 반환하고 더 내려가지 않습니다 |
| 질의 구간이 내 구간을 통째로 덮음 | 저장된 값을 그대로 반환합니다. 여기서 멈추는 것이 O(log N)의 비결입니다 |
| 일부만 겹침 | 두 자식에게 물어보고 결과를 더합니다 |
node 1 [0..4] : 질의 [1..3] 과 일부만 겹침 → 자식에게
├─ node 2 [0..2] : 일부만 겹침 → 자식에게
│ ├─ node 4 [0..1] : 일부만 겹침 → 자식에게
│ │ ├─ node 8 [0..0] : 안 겹침 → 0
│ │ └─ node 9 [1..1] : 통째로 덮임 → 8 ✓
│ └─ node 5 [2..2] : 통째로 덮임 → 4 ✓
└─ node 3 [3..4] : 일부만 겹침 → 자식에게
├─ node 6 [3..3] : 통째로 덮임 → 3 ✓
└─ node 7 [4..4] : 안 겹침 → 0
합계 = 8 + 4 + 3 = 15
여기서 중요한 것은 “통째로 덮임”에서 즉시 멈춘다는 점입니다. 만약 이 조건 없이 리프까지 다 내려간다면 O(N)이 되어 버립니다. 어떤 구간이든 최대 O(log N)개의 노드로 쪼개진다는 것이 세그먼트 트리의 수학적 보장입니다.
3. 변경(update) — O(log N)
arr[1] 을 8에서 10으로 바꿔 봅시다. 순진하게 하면 리프를 고친 뒤 조상들의 합을 다시 계산해야 하지만, 차이(diff)만 전파하면 재계산이 필요 없습니다.
diff = 10 - 8 = 2
node 1 [0..4] : 27 → 29 (+2)
node 2 [0..2] : 17 → 19 (+2)
node 4 [0..1] : 13 → 15 (+2)
node 9 [1..1] : 8 → 10 (+2) ← 목표 리프
바뀐 원소를 포함하는 노드는 루트에서 그 리프까지의 경로 위에 있는 노드들뿐입니다. 그 노드들은 모두 정확히 diff 만큼 커지므로, 내려가면서 더해 주기만 하면 됩니다. 경로 길이가 트리 높이이므로 O(log N)입니다.
이때 원본 배열 nn 을 따로 들고 있어야 합니다. diff 를 구하려면 바뀌기 전 값을 알아야 하기 때문입니다.
전체 코드
import java.util.Scanner;
public class Main {
private static long nn[];
private static long tree[];
public static void main(String[] args) {
var sc = new Scanner(System.in);
var n = sc.nextInt();
var m = sc.nextInt();
var k = sc.nextInt();
m += k; // 변경과 질의가 섞여 들어오므로 합쳐서 돈다
nn = new long[n];
tree = new long[4 * n];
for (int i = 0; i < n; i++) nn[i] = sc.nextInt();
init(nn, tree, 1, 0, n - 1);
while (m-- > 0) {
var a = sc.nextInt();
var b = sc.nextInt();
if (a == 1) { // 변경
var c = sc.nextLong();
var diff = c - nn[b - 1]; // 바뀌기 전 값이 있어야 diff 를 구한다
nn[b - 1] = c;
update(tree, 1, 0, n - 1, b - 1, diff);
} else if (a == 2) { // 구간 합
var c = sc.nextInt();
System.out.println(sum(tree, 1, 0, n - 1, b - 1, c - 1));
}
}
}
private static long init(long[] nn, long[] tree, int node, int start, int end) {
if (start == end) {
return tree[node] = nn[start];
}
return tree[node] = init(nn, tree, node * 2, start, (start + end) / 2)
+ init(nn, tree, node * 2 + 1, (start + end) / 2 + 1, end);
}
private static long sum(long[] tree, int node, int start, int end, int left, int right) {
if (end < left || start > right) { // 전혀 안 겹침
return 0;
}
if (left <= start && end <= right) { // 통째로 덮임 — 여기서 멈춘다
return tree[node];
}
return sum(tree, node * 2, start, (start + end) / 2, left, right)
+ sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
}
private static void update(long[] tree, int node, int start, int end, int index, long diff) {
if (index < start || index > end) return; // 이 노드 아래에 목표 리프가 없다
tree[node] = tree[node] + diff;
if (start != end) {
update(tree, node * 2, start, (start + end) / 2, index, diff);
update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
}
}
}
놓치기 쉬운 부분
- 반드시
long을 씁니다. 원소 하나가 최대 2^63-1 이고 구간 합은 그보다 커질 수 있어int로는 넘칩니다. 트리 배열, 원본 배열, 반환 타입 모두long이어야 합니다. - M과 K를 합쳐서 돕니다. 입력에서 변경 횟수 M과 질의 횟수 K가 따로 주어지지만 두 명령이 순서 없이 섞여 들어오므로,
m += k로 합친 뒤 첫 번째 숫자를 보고 분기합니다. - 인덱스를 0-based 로 바꿔 넘깁니다. 문제 입력은 1부터 세므로
b - 1,c - 1로 변환합니다. 트리 노드 번호(1부터)와 배열 인덱스(0부터)가 서로 다른 체계라는 점을 헷갈리기 쉽습니다. update의index < start || index > end조건이 없으면 목표 리프와 상관없는 가지까지 전부 내려가 O(N)이 됩니다.
복잡도 정리
| 연산 | 시간 | 이유 |
|---|---|---|
| 초기화 | O(N) | 모든 노드를 한 번씩 방문 |
| 구간 합 | O(log N) | 구간이 O(log N)개 노드로 분해 |
| 변경 | O(log N) | 루트에서 리프까지 한 경로만 |
공간은 트리 배열 4N 과 원본 배열 N 입니다.
한 걸음 더
- 구간 전체를 한꺼번에 바꾸는 문제라면 매 원소마다 update를 부르면 O(N log N)이 됩니다. 이때는 레이지 프로퍼게이션(Lazy Propagation) 으로 갱신을 미뤄 두었다가 필요할 때 내려보내 O(log N)으로 처리합니다.
- 구간 합만 필요하고 구현을 줄이고 싶다면 펜윅 트리(Binary Indexed Tree) 가 대안입니다. 메모리는
N+1, 코드는 훨씬 짧지만 구간 최솟값 같은 다른 연산으로 확장하기는 어렵습니다. - 세그먼트 트리가 성립하는 조건은 결합 법칙입니다.
(a+b)+c = a+(b+c)가 성립하기 때문에 구간을 아무렇게나 쪼개 합쳐도 결과가 같습니다. 같은 이유로 최솟값·최댓값·GCD 도 같은 틀로 처리할 수 있습니다.