세그먼트 트리에 대해서 이해한대로 정리해보자!
세그먼트 트리는 전체 구간 중에서 일부 구간에 대한 변경이 있을 때
그 변경으로 인한 변화를 빠르게 알기 위해서 사용한다 ==> 구간탐색을 위해서 사용한다
임의의 배열에 1 2 3 4 5 라는 값이 있고, 이에 대한 세그먼트 트리를 만들기 위해서는
1 2 3 4 5 를 리프노드로 하는 일정범위(구간)에 대한 정보를 알아야 한다
배열을 이용해서 세그먼트트리를 표현해보자!
세그먼트 트리의 대표적인 문제는 구간 합을 해결하는 문제를 예로 들 수 있다.
가장 기본적인 구간 합을 예로 들어서 세그먼트 트리를 설명하려고 한다
세그먼트 트리의 가장 윗 부분의 인덱스(노드번호)를 1로 지정하게 되면,
임의의 노드의 자식노드는 *2, *2+1 의 인덱스를 가지게 된다(완전트리의 형식이기 때문)
루트 노드인 1번 노드는 1,2,3,4,5 에 대한 모든 범위인 [1,5] 에 대한 정보를 가진다.
루트 노드의 자식노드인 2(1*2)번, 3(1*2+1)번 노드는 [1,5] 의 범위에 대한 중간값을 기준으로
각각 [1,3], [4,5] 에 대한 정보를 가지게 된다
-----------------------------------------------------------------------------------------------------------------------------------
가장 먼저 재귀를 통해 세그먼트 트리를 만드는 함수를 살펴보자!
|
1
2
3
4
5
6
7
8
9
10
|
ll segment(int left, int right, int node) {
if (left == right)
return seg[node] = arr[left];
int mid = (left + right) / 2;
seg[node] += segment(left, mid, node * 2);
seg[node] += segment(mid + 1, right, node * 2 + 1);
return seg[node];
}
|
ll 은 long long 을 의미한다.
left , right 는 현재 노드번호(node = 위에서 말한 배열인덱스)가 가지고 있는 정보이다
첫 호출 때는 segment(1,N,1) 으로 호출했다고 볼 수 있다.
left == right 를 만족하게 되면 node번쨰 인덱스의 배열에는 세그먼트트리의 리프노드 값인 실제 값이 들어갈 공간!
그게 아니라면 (left+right)/2 를 통해 재귀를 들어가주면서 += 를 해줌으로써 자식에 대한 총합을 가지게 된다!
이런식으로 모든 범위에 대한 세그먼트 트리를 만들 수 있다.
-------------------------------------------------------------------------------------------------------------------------------
원하는 위치의 값을 다른 값으로 바꾸는 update에 대해서 알아보자
** update 는 세그먼트 트리의 리프노드인 원하는 위치의 값을 바꿈과 동시에
이 리프노드와 관련된 모든 노드의 정보를 바꾸는 작업이다
지금 당장 원하는 위치의 값이 세그먼트 트리의 몆번째 노드에 있는지 알고 있다면
/2를 해가면서 리프노드부터 루트노드까지 올라가면서 값을 변경해주면 된다.
하지만 보통? 문제들은 세그먼트트리의 몆번째 노드에 원하는 값이 있는지 알 수 없다.
그러므로 루트노드부터 쭉 내려가면서 원하는 위치의 리프노드를 찾아가면서 값을 바꿔주면 된다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void update(int node, int left, int right, int change, int val) {
if (!(left <= change && change <= right)) return;
seg[node] += (val - arr[change]);
if (left != right) {
int mid = (left + right) / 2;
update(node * 2, left, mid, change, val);
update(node * 2 + 1, mid + 1, right, change, val);
}
}
|
인자를 순서대로 살펴보면
node => 현재 노드번호(배열인덱스)
left, right => 현재 노드가 가지고 있는 범위
change => 바꾸고싶은 리프노드 위치
val => 바꿀 값
첫번째 if문을 살펴보자
나는 현재 3번째 값을 5로 바꾸고 싶다고 가정했을 때,
현재 탐색 중인 노드의 범위가 3번째위치를 포함하지 않는다면 빠르게 손절한다는 의미이다
[1,5] 의 범위에는 3번째위치가 포함되지만
[1,2], [4,5] 의 범위에는 3번째위치가 포함되지 않는다.
결국 left <= change && change <= right 를 만족하면 현재 세그먼트에 대한 정보를 변경해도 되는 것!
두번째 if문의 의미는 현재 탐색 중인 노드가 리프노드인지 아닌지를 확인하는 것이다
left == right이면 리프노드를 의미하게 되니 더이상 update를 수행할 필요가 없는 것이고,
left != right이면 자식노드에 대한 정보를 update 해줘야한다!
-----------------------------------------------------------------------------------------------------------------------------------
구간 합을 구하는 방법을 살펴보자
다음 예시를 빠르게 이해한다면 코드 역시 빠르게 이해할 수 있다.
리프노드가 아닌 현재 노드는 리프노드들의 정보를 가지고 있다고 했었다.
현재 나는 구간[2,5] 에 대한 정보를 알고싶다.
[1,5] 의 범위는 필요한 정보를 가지고 있는가?
정답은 x 이다. 1에 대한 정보를 가지고 있기 때문 => 불필요한 정보!
[4,5] 의 범위는 필요한 정보를 가지고 있는가?
정답은 o 이다. [2,5] 중에서 [4,5] 에 대한 정보를 가지고 있기 때문이다.
** 불필요한 정보는 버리고 필요한 범위만 가져오는 것이 세그먼트 트리의 구간을 이용하는 기본개념!
** 현재 범위를 left, right 내가 알고 싶은 범위를 s, e 라고 한다면
s 가 left 보다 작거나 같고, e 가 right 보다 크거나 같다면
현재 확인 중인 노드는 알고싶은 [s,e] 에 대한 정보를 가지고 있으니 더이상 탐색할 필요가 없게 된다.
** ex) [2,5] 의 정보를 알고자 하는데 현재 노드가 [4,5]를 가지고 있다면
2<=4 && 5 <= 5 이면 모든 정보를 가지고 있음을 의미함 **
|
1
2
3
4
5
6
7
|
ll sum(int node, int left, int right, int s, int e) {
if (left > e || right < s) return 0;
if (s <= left && e >= right) return seg[node];
int mid = (left + right) / 2;
return sum(node * 2, left, mid, s, e) + sum(node * 2 + 1, mid + 1, right, s, e);
}
|
** 첫번째 if 문은 현재 알고 싶은 범위가 노드가 가진 정보와 관련이 없다면 탐색종료 한다는 의미이다.
** 두번째 if 문은 현재 노드가 가진 범위가 내가 알고싶은 범위에 대한 정보를 모두 포함한다는 의미이다.
** 그렇지 않다면 재귀를 통해 탐색해주면 된다.
'algorithm > algorithm' 카테고리의 다른 글
| 볼록껍질 선분 처리하기 (0) | 2020.02.28 |
|---|---|
| 유클리드 호제법 (0) | 2020.02.28 |
| 선분 교차 판별하기 (0) | 2020.02.02 |
| 삼분 탐색(Ternary search) (0) | 2020.01.16 |
| LCS (0) | 2019.07.04 |