글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree
문제
배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다.
- 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기
- i번째 수를 v로 바꾸기. A[i] = v
수행해야하는 연산은 최대 M번입니다.
세그먼트 트리나 다른 방법을 사용하지 않고 문제를 푼다면, 1번 연산을 수행하는데 O(N), 2번 연산을 수행하는데 O(1)이 걸리게 됩니다. 총 시간 복잡도는 O(NM) + O(M) = O(NM)이 나오게 됩니다.
2번 연산이 없다고 생각해봅시다.
수를 바꾸는 경우가 없기 때문에, 합도 변하지 않습니다. 따라서, 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀 수 있습니다.
S[i] = A[1] + ... + A[i] 라고 했을 때, i~j까지 합은 S[j] - S[i-1]이 됩니다.
i~j까지 합은 A[i] + ... + A[j]인데, S[j] = A[1] + ... + A[j], S[i-1]= A[1] + ... + A[i-1] 이기 때문입니다.
S[0] = A[0];
for (int i=1; i<n; i++) {
S[i] = S[i-1] + A[i];
}
여기서 2번 연산을 하려면, 수가 바뀔때마다 S를 변경해줘야 합니다. 가장 앞에 있는 0번째 수가 바뀐 경우에는 모든 S 배열을 변경해야 하기 때문에, 시간복잡도는 O(N)이 걸리게 됩니다.
따라서, M과 N이 매우 큰 경우에는 시간이 너무 오래걸리게됩니다.
세그먼트 트리
세그먼트 트리를 이용하면, 1번 연산을 O(lgN), 2번 연산도 O(lgN)만에 수행할 수 있습니다.
세그먼트 트리의 리프 노드와 리프 노드가 아닌 다른 노드는 다음과 같은 의미를 가집니다.
- 리프 노드: 배열의 그 수 자체
- 다른 노드: 왼쪽 자식과 오른쪽 자식의 합을 저장함
어떤 노드의 번호가 x일때, 왼쪽 자식의 번호는 2*x, 오른쪽 자식의 번호는 2*x+1이 됩니다.
N = 10인 경우에 세그먼트 트리는 다음과 같습니다.
위의 그림은 각 노드가 저장하고 있는 합의 범위를 나타낸 그림입니다. 여기에 각 노드의 번호를 그림으로 나타내면 다음과 같습니다.
만들기
만약, N이 2의 제곱꼴인 경우에는 Full Binary Tree 입니다. 또, 그 때 높이는 lgN 입니다. 리프 노드가 N개인 Full Binary Tree는 필요한 노드의 개수가 2*N-1개 입니다.
N이 2의 제곱꼴이 아닌 경우에는 높이가 H = $\lceil$lgN$\rceil$ 이고, 총 세그먼트 트리를 만드는데 필요한 배열의 크기는 2^(H+1) - 1개가 됩니다.
다음과 같은 과정을 거쳐서 Segment Tree를 만들 수 있습니다.
// a: 배열 a
// tree: 세그먼트 트리
// node: 세그먼트 트리 노드 번호
// node가 담당하는 합의 범위가 start ~ end
long long init(vector<long long> &a, vector<long long> &tree, int node, int start, int end) {
if (start == end) {
return tree[node] = a[start];
} else {
return tree[node] = init(a, tree, node*2, start, (start+end)/2) + init(a, tree, node*2+1, (start+end)/2+1, end);
}
}
start == end
인 경우는 node
가 리프 노드인 경우입니다. 리프 노드는 배열의 그 원소를 가져야 하기 때문에 tree[node] = a[start]
가 됩니다.
node
의 왼쪽 자식은 node*2
, 오른쪽 자식은 node*2+1
이 됩니다. 또, node
가 담당하는 구간이 [start,end]
라면 왼쪽 자식은 [start,(start+end)/2]
, 오른쪽 자식은 [(start+end)/2+1,end]
를 담당해야 합니다. 따라서, 재귀 함수를 이용해서 왼쪽 자식과 오른쪽 자식 트리를 만들고, 그 합을 저장해야 합니다.
합 찾기
구간 left, right이 주어졌을 때, 합을 찾으려면 루트부터 트리를 순회하면서 각 노드가 담당하는 구간과 left, right 사이의 관계를 살펴봐야 합니다.
예를 들어, 0~9까지 합을 구하는 경우는 루트 노드 하나만으로 합을 알 수 있습니다.
2~4까지 합을 구하는 경우는 다음과 같습니다.
5~8까지 합을 구하는 경우는 다음과 같습니다.
3~9까지 합을 구하는 경우는 다음과 같습니다.
node
가 담당하고 있는 구간이 [start,end]
이고, 합을 구해야하는 구간이 [left,right]
이라면 다음과 같이 4가지 경우로 나누어질 수 있습니다.
[left,right]
와[start,end]
가 겹치지 않는 경우[left,right]
가[start,end]
를 완전히 포함하는 경우[start,end]
가[left,right]
를 완전히 포함하는 경우[left,right]
와[start,end]
가 겹쳐져 있는 경우 (1, 2, 3 제외한 나머지 경우)
1번 경우에는 if (left > end || right < start)
로 나타낼 수 있습니다. left > end
는 [start,end]
뒤에 [left,right]
가 있는 경우이고, right < start
는 [start,end]
앞에 [left,right]
가 있는 경우입니다. 이 경우에는 겹치지 않기 때문에, 더 이상 탐색을 이어나갈 필요가 없습니다. 따라서 0
을 리턴해 탐색을 종료합니다.
2번 경우는 if (left <= start && end <= right)
로 나타낼 수 있습니다. 이 경우도 더 이상 탐색을 이어나갈 필요가 없습니다. 구해야하는 합의 범위는 [left,right]
인데, [start,end]
는 그 범위에 모두 포함되고, 그 node
의 자식도 모두 포함되기 때문에 더 이상 호출을 하는 것은 비효율적입니다. 따라서, tree[node]
를 리턴해 탐색을 종료합니다.
3번과 4번의 경우에는 왼쪽 자식과 오른쪽 자식을 루트로 하는 트리에서 다시 탐색을 시작해야 합니다.
// node가 담당하는 구간이 start~end이고, 구해야하는 합의 범위는 left~right
long long sum(vector<long long> &tree, int node, int start, int end, int left, int right) {
if (left > end || right < start) {
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);
}
수 변경하기
중간에 어떤 수를 변경한다면, 그 숫자가 포함된 구간을 담당하는 노드를 모두 변경해줘야 합니다.
다음은 3번째 수를 변경할 때, 변경해야 하는 구간을 나타냅니다.
다음 그림은 5를 변경할 때입니다.
index
번째 수를 val
로 변경한다면, 그 수가 얼마만큼 변했는지를 알아야 합니다. 이 수를 diff
라고 하면, diff = val - a[index]
로 쉽게 구할 수 있습니다.
수 변경은 2가지 경우가 있습니다.
[start,end]
에index
가 포함되는 경우[start,end]
에index
가 포함되지 않는 경우
node
의 구간에 포함되는 경우에는 diff
만큼 증가시켜 합을 변경해 줄 수 있습니다. tree[node] = tree[node] + diff
포함되지 않는 경우는 그 자식도 index
가 포함되지 않기 때문에, 탐색을 중단해야 합니다.
void update(vector<long long> &tree, int node, int start, int end, int index, long 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);
}
}
리프 노드가 아닌 경우에는 자식도 변경해줘야 하기 때문에, start != end
로 리프 노드인지 검사를 해야 합니다.
세그먼트 트리를 이용해서 2042번 문제: 구간 합 구하기 번을 풀 수 있습니다. 최소값, 최대값도 합을 구하는 세그먼트 트리를 응용해서 구현할 수 있습니다. 10868번 문제: 최솟값, 2357번 문제: 최솟값과 최댓값
다음은 2042번을 푸는 소스입니다.
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
long long init(vector<long long> &a, vector<long long> &tree, int node, int start, int end) {
if (start == end) {
return tree[node] = a[start];
} else {
return tree[node] = init(a, tree, node*2, start, (start+end)/2) + init(a, tree, node*2+1, (start+end)/2+1, end);
}
}
void update(vector<long long> &tree, int node, int start, int end, int index, long 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 long sum(vector<long long> &tree, int node, int start, int end, int left, int right) {
if (left > end || right < start) {
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);
}
int main() {
int n, m, k;
scanf("%d %d %d",&n,&m,&k);
vector<long long> a(n);
int h = (int)ceil(log2(n));
int tree_size = (1 << (h+1));
vector<long long> tree(tree_size);
m += k;
for (int i=0; i<n; i++) {
scanf("%lld",&a[i]);
}
init(a, tree, 1, 0, n-1);
while (m--) {
int t1,t2,t3;
scanf("%d",&t1);
if (t1 == 1) {
int t2;
long long t3;
scanf("%d %lld",&t2,&t3);
t2-=1;
long long diff = t3-a[t2];
a[t2] = t3;
update(tree, 1, 0, n-1, t2, diff);
} else if (t1 == 2) {
int t2,t3;
scanf("%d %d",&t2,&t3);
printf("%lld\n",sum(tree, 1, 0, n-1, t2-1, t3-1));
}
}
return 0;
}
댓글 (39개) 댓글 쓰기
yukariko 8년 전
좋아요!
traveler 8년 전
좋아요!!!!!!!!!
temp 8년 전
좋은 방법이네요.
mountainlion0523 8년 전
C로 트리를 배열로 구성할 경우 배열 크기가 부담이 될 수 되겠네요; C로 구현하는걸 선호해서;;;
yukariko 8년 전
C++에서 사용하는 vector도 배열입니다. 따라서 세그먼트 트리 배열 구현에 C++, C 구분은 딱히 없어보입니다.
hananakajima 7년 전
이 글을 보고 암이 나았습니다.
fakingate 4년 전
이하동문입니다
201023777 7년 전
세그먼트 트리 배우러 왔습니다
kingkk31 7년 전
감사합니다ㅜㅜ
taso 7년 전
재밌어요!
peter1201 7년 전
많은 도움이 됬습니다. 감사합니다 !
pr0v3rbs 7년 전
좋은 글 잘 봤습니다.
heehcs 7년 전
고맙습니다.
kim2552 7년 전
운영자님 정말 감사드립니다!^^ 밥이라도 사드리고싶네요 ^^
jjhhyper 7년 전
이런 알고리즘 설명 너무 감사해요!! 다른 알고리즘도 있으면 좋겠당!!
jaegu88 7년 전
정말 명쾌한 설명이네요~
doduck 6년 전
update 전에 a[t2] = t3; 부분이 있고 없고에 따라서 정답 여부가 달라지는데 실제 처음 받은 a 배열은 update 하는데 뭐가 달라지게 되는건가요?
inspire12 6년 전
diff 를 구할 때 쓰기 때문입니다. 만약에 a[t2] = t3을 안하면 예전 값을 변화량으로 계산해서 다음에 트리만들때 잘못 값을 구하게 됩니다.
k71019555 6년 전
덕분에 이해했습니다
dbfldkfdbgml 5년 전
감사합니다 펜윅까지 쭉쭉 보고 있습니다
leewj1025 4년 전
이 글을 읽고 많은 도움이 되어 뇌사했던 뇌가 깨어났습니다. 야호!!!!
migu554 4년 전
유용한 정보 감사합니다!!
iron1209 4년 전
이 글을 군대에서 읽고 주말에 자다가 일어나서 감탄을 했습니다.
aj4941 4년 전
명쾌한 설명 덕분에 완벽히 이해했네요!! 감사합니다!
kgj291 4년 전
나를 이해시키다니 대단한 녀석이군
djm03178 3년 전
이 글을 보고 세그먼트 트리를 처음 접하는 분이 많을 것 같아서 팁을 하나 써봅니다.
개인적으로는 구간 합 구하기 문제에서 diff를 구해 그 변화를 반영하는 것보다는 원소의 값을 바꾸는 업데이트 자체를 세그먼트 트리가 수행하도록 하는 편이 더 간단하고 이해가 쉽다고 생각합니다.
예를 들어 본문의 그림에서 5번 원소를 업데이트 하는 경우 update 함수의 인자로 diff 대신 어떤 값으로 업데이트 하려는지 (k)를 전달해 주면, 리프 노드에서는
tree[node] = k
; 를 수행해주면 되며, 그 부모 / 조상 노드들에서는tree[node] = tree[node * 2] + tree[node * 2 + 1];
을 수행하여 업데이트 해주면 됩니다. 이렇게 하면 매번 a 배열을 업데이트 해줘야 하는 번거로움도 없어지며, 이전 값을 기억하고 있어야 한다는 부담도 덜게 됩니다. 또한 세그먼트 트리의 각 노드가 항상 두 자식의 합을 가지고 있다는 의미 또한 더 명확해집니다.물론 이 문제와는 관계 없이 변화량을 세그먼트 트리에 적용하는 테크닉 자체는 유용하게 사용될 수 있는 곳은 많이 있으니 알아두어도 나쁠 건 없습니다.
iskang5532 3년 전
잘 보고 갑니다.
baekjoon 3년 전
말씀하신대로 저도 세그먼트 트리를 구현할 때는 원소의 값을 바꾸는 업데이트 자체를 사용하는데, 이 글을 왜
diff
를 이용하게 작성했는지 잘 모르겠습니다. 업데이트를 해야겠습니다.porsch 2년 전
https://www.acmicpc.net/blog/view/26 본문에서 이어지는 세그먼트트리 설명 2번글인데, 게으른 전파를 설명하고 있습니다. 게으른 전파를 이해하려면 탑다운으로 변화를 반영할 수 있어야 하므로 diff를 사용하는 개념을 설명하셨다고 생각이 되네요. 굳이 게으른 전파를 사용할 필요가 없는 문제를 풀 때는 말씀하신 방법으로 접근하는 것이 훨씬 간편한 것 같습니다.
baekjoon 2년 전
안녕하세요. Lazy propagation 을 설명하기 위해 이 글을 그렇게 설명한 것이 맞는 것 같습니다. 저보다 저를 더 잘 아시는 군요
ktasha45 2년 전
와.. 이런 방법이. 통찰이 엄청나십니다 감사합니다
huozuyinshua 2년 전
감사합니다
literate_t 2년 전
세그먼트 트리를 이해하는데 많은 도움을 받았습니다. 감사합니다.
ktasha45 2년 전
정말 감사합니다. 이보다 직관적일 수가 없네요!! 도움 많이 받았습니다.
shoo040113 1년 전
https://book.acmicpc.net/ds/segment-tree 위 글 소스 4 부분의 두 함수명이 동일합니다. 아래 코드와 같이 수정해야 할 것 같습니다.
shoo040113 1년 전
추가로, 소스 4 바로 위 설명 또한 "소스 4의 update(a, tree, index, val)은 index번째를 val로 변경하는 코드이고," --> "소스 4의 update(a, tree, n, index, val)은 index번째를 val로 변경하는 코드이고," 와 같이 수정해야 할 것 같습니다.
djm03178 1년 전
함수명이 동일해도 됩니다. C++에는 동일한 함수 이름에 인자 목록만 달리하여 서로 다른 함수로 간주되게 할 수 있는 함수 오버로딩이라는 것이 있습니다. 예를 들어 max 함수가 int, long, double 등 다양한 자료형에 대한 버전이 존재하는 것도 함수 오버로딩입니다.
shoo040113 1년 전
헉.... 그런 것도 있었군요.. 제 공부가 많이 부족했습니다 . 알려주셔서 감사합니다
dlwjsgud12 2달 전
글 설명 문맥상으로는 shoo040113 님께서 말씀하신대로 함수명을 바꾸는 것이 맞는데 C++ 소스코드만 함수명이 동일하고 Java 와 Python 소스코드는 제대로 되어 있는 것 같습니다