[자료구조] Segment Tree(세그먼트 트리) c++ 구현, 설명

세그먼트 트리

세그먼트 트리는 이진 트리로 구성하면됨.

구간의 길이가 1인 구간은 리프 노드가 되고, 나머지 노드는 자식 노드를 합친 구간 합을 들고 있음.

 

배열의 길이가 N이라면 세그먼트 트리의 노드 개수는 2N - 1 개가 됨.

루트를 배열 1번 부터 시작 한다고 하면 필요한 배열의 길이는 2N이 된다.

 

Init

처음 세그먼트 배열을 초기화 할 때는 N부터 시작해서 길이가 1인 구간을 N개 만큼 채워넣어준다.

그 후 N-1부터 자식노드의 두 개를 합쳐서 구간의 합을 구하면서 위로 올라가면 위과 같은 그림이 나오게 된다.

 

Update

만약 중간에 배열의 값이 바뀐다면 노드의 값을 바꿔준 후 부모쪽으로 올라가며 다시 구간 합을 구해서 넣어주면 된다.

 

[l,r) 구간 합 찾기

구간 합 찾는 과정은 구간의 시작점 노드 l과 끝점의 다음 노드 r에서 부모 노드로 올라가면서, 해당 노드에 적힌 값을 결과값에 더해야하면 더하고, 아니면 건너뛰면 된다.

이때 l노드가 부모 노드의 왼쪽 자식일 경우(인덱스가 짝수)이면 그 위쪽 부모 노드에서 더해도 포함이 되어 상관이 없기 때문에 넘어가 준다. 반면 부모의 오른쪽 자식일 경우(인덱스 홀수)면 그대로 부모로 올라가면 더하면 안되는 구간이 포함이 되기 때문에 먼저 더해준다. 

 

이때 중요한 것은 l 같은 경우 시작 점이기 때문에 만약 홀수라면 더해주고 노드가 오른쪽으로 이동해주고 그 부모로 이동해야 한다.

r같은 경우는 끝점이기 때문에 홀수일 경우 먼저 -1을 해주어서 포함되는 구간으로 이동 후 구간합을 더한 후 그 부모로 이동을 해주어야 한다.

그 후 l과 r이 같아지면 작업이 끝이 나게된다.

 

이 부분은 직접 그림을 그린 후 하나씩 해보면 이해가 쉽다.

 

노드 순서

위 그림에서 볼 수 있듯이 노드의 순서가 섞여있다. 왼쪽 자식이 오른쪽 구간을, 오른쪽 자식이 왼쪽 구간을 나타내는 경우도 있고 중간이 끊긴 구간을 나타내는 노드도 있음.

 

그래서 포화이진트리모양을 이용해서 순서를 정갈하게 해줄 수 있음.

트리에서 첫번째 리프노드의 인덱스를 구해주고 그 리프노드부터 채워주는 것이다.

그리고 나머지 리프노드를 더미 노드로 두고 채워주면 된다.

이 때 리프 노드의 인덱스는 2의 거듭제곱이 되어야 한다.

그래서 리프노드의 시작 인덱스는 N <= 2^(k-1) 를 만족할 수 있는 k의 가장 작은 값이 되면된다.

리프노드의 마지막 인덱스는 2^k -1이 되기 때문에 세그먼트 트리의 개수는 2^k로 잡아주면 된다.

 

응용 문제

각 구간에서의 최대 값, 최소 값을 구하는 세그먼트 트리 구성하기.

 

전체 코드는 github에 업로드 

1. 구간 합 구하는 세그먼트 트리.

2. 각 구간에서의 최대 값, 최소 값을 구하는 세그먼트 트리.

-> https://github.com/goragoraki/Data-Structure