Segment Tree란?
Segment Tree(구간 트리)는 각 구간을 이진 트리로 관리하여 원소의 변경 혹은 구간의 연산을 효율적으로 처리할 수 있는 자료구조 입니다.
먼저 Segment Tree가 대표적으로 어떻게 활용되는 지 알아보겠습니다. 아래 문제를 해결해봅시다.
길이가 \(N\)인 배열 \(A\)가 주어지고, 아래의 쿼리를 효율적으로 처리해야 됩니다.
1. \([l, r]\) 구간의 합 구하기
2. \(i\)번째 수를 \(x\)로 변경하기
Naive하게 접근하면 \(1\)번 쿼리는 \(O(N)\), \(2\)번 쿼리는 \(O(1)\)에 처리할 수 있습니다. 하지만 Segment Tree는 \(1\), \(2\)번 쿼리 모두를 \(O(logN)\)에 처리할 수 있습니다.
아이디어
Segment Tree의 아이디어를 살펴봅시다.
\(N = 8\), \(A = [5, 6, 4, 8 ,1 ,2, 6, 8]\)가 주어질 때 Segment Tree를 만들어 보겠습니다.
위의 사진 처럼 각 정점은 관리하고 있는 구간과 구간의 합을 저장하고 있습니다. 핵심 아이디어는 나뉘어져 있는 구간을 잘 활용하여 처리하는 것입니다.
1번 쿼리
\(1\)번 쿼리로 \([l=3, r=5]\)가 주어질 때, Segment Tree로 처리해봅시다. 아래의 사진은 쿼리를 처리할 때 탐색하는 정점입니다.
쿼리로 주어진 구간 \([l, r]\)을 Segment Tree에서 나뉘어진 구간을 여러개 합하여서 나타내어 구간의 합을 구하여도 답이 변하지 않습니다.
\([l, r]\)을 Segment Tree에서 나뉘어진 구간으로 최소 개수로 나타내어 봅시다. 아래의 방법은 \([0, N-1]\) 구간을 재귀로 분할 정복하듯이 나뉘면서 \([l, r]\)에 포함되는 구간을 찾아갑니다.
1. 변수 \(s, e\)를 정의한다. 이 변수는 현재 정점이 Segment Tree에서 관리하고 있는 구간이다. 초기값은 \(s=0, e=N-1\)이다.
2. \([s, e]\)가 \([l, r]\)에 포함된다면 현재 정점에 저장된 합을 반환한다. \((l <= s && e <= r)\)
3. \([s, e]\)가 \([l, r]\)에 완전히 벗어났다면 \(0\)을 반환한다. \((r < s || e < l)\)
4. \(2, 3\)번의 경우가 아닌 경우, \([s, \frac{s+e}{2}], [\frac{s+e}{2}+1, e]\)로 구간을 나누어 \(2\)번 과정으로 이동한다.
이 방법으로 진행하면 정답을 올바르게 구할 수 있습니다. 그리고 놀라운 사실은 여기서 탐색되는 구간의 개수가 \(logN\)개입니다.
잘 생각해보면 구간 \([l, r]\)을 어떤 \(2^k\) 길이의 구간으로 여럿 나눈다고 생각할 수 있습니다. 그렇다면 \([l, r]\)이 분리된 구간의 개수는 \(logN\)개 정도입니다. 분리된 구간을 Segment Tree에서 찾아 가는 것은 리프 노드가 \(logN\)개의 트리를 순회하는 것과 같으므로 최대 \(2logN\)개까지 탐색할 것입니다.
이 아이디어를 사용하면 \(1\)번 쿼리를 \(logN\)에 처리할 수 있습니다.
2번 쿼리
\(2\)번 쿼리를 살펴봅시다. \(i\)가 포함된 구간을 모두 업데이트하면 됩니다. \(i=6\)이라면 아래와 같이 정점을 탐색합니다.
아래와 같이 탐색을 하시면 됩니다.
1. 변수 \(s, e\)를 정의한다. 이 변수는 현재 정점이 Segment Tree에서 관리하고 있는 구간이다. 초기값은 \(s=0, e=N-1\)이다.
2. \([s, e]\)가 \([i, i]\)이면 현재 정점에 저장된 합을 \(x\)로 변경한다. \((s == e)\)
3. \([s, e]\)가 \([i, i]\)에 완전히 벗어났다면 정점에 저장된 합을 반환한다. \((i < s || e < i)\)
4. \(2, 3\)번의 경우가 아닌 경우, \([s, \frac{s+e}{2}], [\frac{s+e}{2}+1, e]\)로 구간을 나누어 \(2\)번 과정으로 이동한 뒤, 반환된 두 값을 \([s, e]\)의 합으로 업데이트한다.
\(i\)가 포함된 구간을 잘 생각해보면 \(logN\)개입니다.
그러므로 Segment Tree로 \(1, 2\)번 쿼리를 \(logN\)에 처리할 수 있습니다.
구현
구현은 크게 재귀 방법과 반복문 방법이 있는데, 재귀 방식으로 설명드리겠습니다.
구간을 분할 정복 하듯이 \(2\)개의 구간으로 나눕니다. 그렇다면 균형잡힌 이진트리가 구성됩니다.
현재 정점의 번호가 \(num\)일 때 이진 트리에서는 좌측 자식 노드는 \(2*num\)으로 배정되고, 우측 자식 노드는 \(2*num+1\)으로 배정됩니다.
쿼리같은 경우에는 위에 설명된 방법으로 구현하시면 됩니다. 자세한 구현 사항은 제가 주로 사용하는 Segment Tree의 구현을 참고해주세요.
struct SegmentTree
{
int n;
vector<int> seg;
void Init(int _n)
{
n = _n;
//이진 트리이므로 4배로 잡아준다.
seg.resize(4 * n);
}
int update(int num, int s, int e, int idx, int diff)
{
//현재 구간이 idx를 포함하지 않는 경우
if (idx < s || e < idx) return seg[num];
//현재 구간이 idx인 경우
if (s == e) return seg[num] = diff;
int mid = (s + e) / 2;
//두 개의 구간으로 나뉘어 현재 구간의 값을 업데이트 한다.
return seg[num] = update(2*num, s, mid, idx, diff) + update(2*num+1, mid+1, e, idx, diff);
}
void update(int idx, int diff) { update(1, 0, n-1, idx, diff); }
int query(int num, int s, int e, int l, int r)
{
//현재 구간이 [l, r]에서 완전히 벗어난 경우
if (r < s || e < l) return 0;
//현재 구간이 [l, r]에 포함된 경우
if (l <= s && e <= r) return seg[num];
int mid = s + e >> 1;
//두 개의 구간으로 나뉘어 구간에 포함된 합을 구한다.
return query(2 * num, s, mid, l, r) + query(2*num+1, mid+1, e, l, r);
}
int query(int l, int r) { return query(1, 0, n-1, l, r); }
};
또한 아주 중요한 성질이 있는 데 각 구간의 연산이 결합 법칙이 성립하면 Segment Tree로 처리할 수 있습니다. 그리고 특수한 경우에는 리프 노드의 구간 길이를 1보다 더 크게 잡을 수도 있습니다.
Segment Tree는 더 많은 종류의 구간 연산을 효율적으로 처리하기 위해 다양한 형태가 있습니다. 여러 차원을 관리하기 위한 다차원 Segment Tree, 구간 업데이트를 위한 Lazy Segment Tree, 이전 Tree의 상태를 모두 보존하는 Persistent Segment Tree, 특수한 구간 연산을 위한 Segment Tree Beats 등 다양하게 있습니다.
추천 문제
Easy
| 번호 | 이름 | 풀이 | 링크 |
| 2042 | 구간 합 구하기 | ||
| 2357 | 최소값과 최댓값 | ||
| 11505 | 구간 곱 구하기 | ||
| 3653 | 영화 수집 | ||
| 10090 | Counting Inversions | ||
| 1517 | 버블 소트 | ||
| 16975 | 수열과 쿼리 21 |
Normal
| 번호 | 이름 | 풀이 | 링크 |
| 1168 | 요세푸스 문제 2 | ||
| 1280 | 나무 심기 | ||
| 20314 | 대홍수 | ||
| 9345 | 디지털 비디오 디스크(DVDs) | ||
| 20052 | 괄호 문자열 ? | \(( = 1\), \() =\) -\(1\) 으로 치환하고 구간합 \(psum\)을 만들어 봅시다. 그렇다면 어떤 구간 \([l, r]\)이 올바른 괄호인 충분 조건은 아래와 같습니다. 1. \(psum_l = psum_r+1\) 2. \(psum_r \le min([l, r])\) \(2\)번 조건은 Minimum Segment Tree로 효율적으로 처리할 수 있습니다. |
풀이 |
| 5419 | 북서풍 | ||
| 3392 | 화성 지도 | ||
| 17411 | 가장 긴 증가하는 부분 수열6 | ||
| 2236 | 굉장한 학생 | ||
| 2472 | 체인점 |
Hard
| 번호 | 이름 | 풀이 | 링크 |
| 7626 | 직사각형 | ||
| 17407 | 괄호 문자열과 쿼리 | ||
| 15561 | 구간 합 최대? 2 | ||
| 16993 | 연속합과 쿼리 | ||
| 10167 | 금광 | ||
| 17138 | 습격자 초라기와 쿼리 (Easy) | ||
| 20177 | Stock Analysis | ||
| 15506 | 정원사 | Segment Tree의 리프 노드에느 우선 순위 큐를 관리하고 1번 쿼리가 들어올 때마다 우선 순위 큐에 넣습니다. 그리고 정점의 값에는 {현재 우선 순위 큐에서 가장 큰값, 인덱스, 우선 순위 큐 크기}를 저장 해두고, 쿼리할 때 마다 우선 순위 큐에서 가장 큰 값을 가진 인덱스를 반환 합시다. 또한 우선 순위 큐 크기도 합으로 관리해줄 수 있습니다. 그렇다면 2번 쿼리는 구간 내에서 가장 큰 값을 가져오고 쿼리의 조건에 맞다면 리프노드의 우선 순위 큐에서 하나를 빼줍니다. 이런식으로 2번 쿼리를 처리할 수 있습니다. 3번 쿼리는 단순히 구간합을 구합니다. |
|
| 17424 | 2xN 타일링과 쿼리 | ||
| 17668 | 시험 | ||
| 17704 | Matryoshka | \((a, b) (c, d) a < c, b < d\) 를 만족하는 점들을 연결할 때 연결된 컴포넌트의 최소 개수를 구하는 문제입니다. 이 문제는 Dilworth's theorem에 의해서 \((a, b) (c, d) a < c, b > d\)의 LIS를 구하는 문제와 동치입니다. 각 쿼리를 잘 스위핑 하면서 Segment Tree로 위의 LIS를 잘 구해주시면 됩니다. |
풀이 |
| 17743 | Collecting Images is Fun | ||
| 3990 | 화면 보호기 | ||
| 18193 | 비행기 타고 가요 | 문제 설명대로 그래프를 구성하면 간선이 상당히 많고, Dijkstra를 시행하기에는 무리입니다. 관찰할 수 있는 사실은 간선이 하나의 구간으로 나타나는 점입니다. 구간은 Segment Tree의 아이디어 처럼 \(logN\)개의 구간으로 나뉠 수 있습니다. 그렇다면 그래프를 Segment Tree처럼 나타내면 각 정점당 간선을 \(logN\)개로 줄일 수 있습니다. 또한 정점 사이를 연결할 때 \(log^2N\)개의 간선이 사용될 때 있는 데 이 경우에는 더미노드를 만들어 \(logN\)개로 바꾸어줄 수 있습니다. 위와 같이 그래프를 구성하면 정점당 간선을 \(logN\)개로 효율적으로 Dijkstra를 시행할 수 있습니다. |
|
| 8874 | 웜뱃 |