1. 세그먼트 트리란?
•
세그먼트 트리(Segment Tree)는 구간의 합, 최솟값, 최댓값 등을 빠르게 구할 때 사용하는 자료구조이다.
세그먼트 트리 vs 누적합 비교
2. 트리 만들기
•
위와 같은 숫자들의 구간 합을 구하기 위해서 2개씩 합계를 구한다.
•
2개의 합계를 또 2개씩 묶는다.
•
이번에도 또 2개씩 묶는다. 문제는 앞의 2개를 묶으면 하나가 남는다. 이럴 때에는 뒤에 0으로 되어있는 합계가 있다고 생각하면 된다.
•
마지막으로 2개의 합계를 구하면 세그먼트 트리가 완성된다.
3. 구간 합 구하기
•
이제 4번째 숫자인 4부터 11번째 숫자인 11까지의 합계를 구해보자.
•
먼저, 전체 범위인 1부터 16까지를 확인한다. 4부터 11까지이기 때문에 범위를 줄여줄 필요가 있다.
•
따라서, 이분 탐색처럼 두 부분으로 나누어 다시 탐색한다.
•
1부터 8까지 범위 확인 결과 아직 4와 11 범위 밖의 값이 존재하기 때문에 한 단계 안으로 더 들어간다.
•
9부터 16까지 범위 확인 결과 아직 4와 11 범위 밖의 값이 존재하기 때문에 마찬가지로 더 들어간다.
•
1부터 4까지 범위 안에는 4가 포함 되어 있기 때문에 한 단계 더 들어간다.
•
5부터 8까지는 전체 구하려는 범위인 4와 11 사이 범위에 포함되어 있기 때문에 더 이상 탐색할 필요가 없다.
•
9부터 12까지는 구하려는 범위 11보다 크기 때문에 한 단계 더 들어간다.
•
13부터 16은 범위 밖에 있기 때문에 더 이상 탐색할 필요가 없다.
•
1부터 2는 범위 밖에 있기 때문에 더 이상 탐색할 필요가 없다.
•
3부터 4는 3이 범위 밖에 있기 때문에 한 단계 더 들어간다.
•
이미 범위 안을 확인했던 5부터 8은 넘어간다.
•
9부터 10은 범위 안에 있기 때문에 포함한다.
•
11부터 12는 12가 범위 밖에 있기 때문에 한 단계 더 들어간다.
•
최종적으로 모든 범위를 구했다. 이제 4 + 32 + 9 + 11을 하면 4부터 11까지의 범위의 합계를 구할 수 있다.
•
그림으로 쉽게 표현 하였지만 각각의 위치를 구하는 것도 쉽지 않다. 아래부터 1번 인덱스로 하는 트리 형태를 떠올려야 한다.
◦
전체 범위의 값은 1번 인덱스에 저장된다.
◦
1번 부터 8번까지는 2번 인덱스가 된다.
◦
9번부터 16번 인덱스는 3번 인덱스가 된다.
◦
어떤 범위가 n번 인덱스라면 그 하위 인덱스는 2n과 2n + 1번 인덱스가 된다.
•
여기서는 전체가 16개의 범위를 뜻하지만 데이터의 개수에 따라 전체의 범위가 변한다.
◦
데이터가 4개라면 전체가 1부터 4까지가 되는 것이고
◦
데이터가 100개라면 전체 범위는 데이터 100개를 포함할 수 있는 2의 제곱수인 128개가 된다.
3. 값 업데이트 하기
•
누적합을 사용해서 구간합을 구하는 것은 세그먼트 트리보다 빠를 수 있다.
•
하지만 값의 변경이 생긴다면 누적합으로는 해결이 불가능 하다.
◦
어떤 값이 변경될 때마다 매번 누적합을 다시 구해줘야 하기 때문이다.
•
하지만, 세그먼트 트리를 이용하면 몇 개의 숫자만 변경하면 된다.
•
첫 번째 값인 10을 15로 변경해보자. 값이 10에서 15로 5가 커졌다.
•
10이 포함된 라인의 값 모두에 5씩 더해주면 된다.
•
이렇게 자신이 포함된 상위 노드의 숫자들만 5씩 크게 만들면 문제가 해결된다.
•
중간의 7번째 인덱스의 값인 7을 3으로 변경해보자. 7보다 4 작아졌기 때문에 다음과 같이 해당 라인의 숫자들만 변경해주면 된다.
