[문제해결기법] 6. 세그먼트 트리

1. Segment Tree

부분합 문제에서 응용 가능

생성 코드

 

2. 합을 구하는 코드

[start, end]의 합을 구하려면 루트부터 시작하여 다음을 점검한다. 노드가 나타내는 구간이 [left, right]라면 다음의 4가지 경우가 가능하다. 각 경우마다 처리는 다음과 같다.

(1) [start, end]와 [left, right]가 겹치지 않음

    -> 할 일이 없다

(2) [start, end]가 [left, right]를 포함

    -> 미리 구해둔 [left, right]의 합을 사용한다.

(3) [start, end]를 [left, right]가 포함

    -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다.

(4) [start, end]가 [left, right]와 포함관계는 없지만 겹침

    -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다.

 

예제 ) Sum(2,8) = ?

 

합을 구하는 함수

 

3. 갱신 (update)

index위치의 수를 diff만큼 바꾸었다면 트리는 Top-down 형식으로 갱신한다.

루트에서 node=1이고, 이 노드는 [start, end] 구간의 합을 저장한다.

index가 [start, end] 범위 안에 없다면 고려할 필요가 없고,

범위에 있다면 이 노드에 저장된 값을 diff만큼 늘리고, 똑같은 과정을 왼쪽/오른쪽 자식에 반복한다.

 

업데이트 함수

 

4. 점 위의 선분 수 세기

구간 [0,N] 위의 선분 n개가 주어지고, 가장 많이 중복되는 선분의 수를 찾는 문제

(1) brute force -> 각 점마다 자신 위를 지나는 선분의 수 세기 : O(Nn)

(2) line sweeping -> O(n log n)

점 -> 구간

구간의 끝마다 선분이 시작하면 +1, 끝나면 -1을 해준다

2 : +1

5 : +1

11 : -1

11 : -1

...

72 : +1

85 : +1

 

이렇게 순회를 해주면 각 구간의 부분합이 구해진다. 이 값이 가장 큰 구간이 가장 많은 선분이 중복되는 구간이다.

라인스위핑 시 정렬하는데 O(n log n), start에 +1을 하고 end에서 -1을 해주는데 2번 순회하므로 O(2n).

총 O(n log n) 소요.

 

(3) 세그먼트 트리 : O(n log n)

구간이 입력으로 주어지고, 구간 사이 선분의 개수를 묻는다면?

모든 선분을 탐색하기 위해 세그먼트 트리를 이용함.

 

노드를 구간으로 잡은 세그먼트를 만들고, 선분을 저장한다

set을 쓰는 이유는 중복 제거가 되므로 같은 구간이 겹친다해도 문제가 생기지 않기 때문.

inserting을 할 때는 해당 선분을 딱 맞게 포함하는 마지막 구간까지 내려가면서 탐색하면 된다

해당 선분을 포함하지 않는 자식에는 질의하지 않는다.

중간에 구간이 나뉠수도 있는데, 그럼 두 구간에 모두 저장한다.

 

O(n log n) = 트리 생성 시간

세그먼트 트리 탐색하면서 지나간 선분 수를 세는데에 O(n), 총 O(n log n)

 

 

5. 또다른 문제 : 점 위의 가장 긴 선분

abs(왼쪽값 - 오른쪽값)으로 선분의 길이를 구할 수 있다.

 

ex: 점 24 위의 가장 긴 선분?

-> 24를 포함하는 구간인 23,25 위의 가장 긴 선분이 답이 된다.

 

구간에 포함되는 선분은 2개인데, abs(17-31) < abs(23-53) 이므로 [23, 53]이 최장선분이다.

 

선분이 n개 있으니 세그먼트 트리의 leaves = O(n)

노드 수 = O(n)

높이 = O(log n)

하나의 선분은 최대 O(log n)개의 노드에 저장

전체 메모리 사용량 = O(n log n) = 트리 생성 시간

점을 찾는데에 O(log n), 총 O(n log n)