이진 트리 구조로 구간을 분할하고 각 구간 별 최적값을 미리 저장해 주어지는 쿼리에 따라 특정 구간에 대한 최적값을 업데이트하거나 구간에 대한 최적값을 연산하는 자료구조다.
구간 별 최적값을 미리 저장해놓는다는 점에서 누적합과 비슷하지만 세그먼트 트리는 구간을 단순 순차가 아닌 이진 트리 구조로 분할한다는 점이 가장 큰 차이점이다.
이진 트리 구조를 취함으로써 각 구간들에 대한 업데이트와 연산을 모두 log(N)에 완료할 수 있다.
두 자료 구조를 그림으로 비교해보면 아래와 같다.
세그먼트 트리 구조를 나타낸 그림이다.
전체 구간을 의미하는 S1을 루트 노드로 하는 이진 트리 구조다. 맨 마지막 리프 노드에는 주어진 배열 값이 그대로 들어가게 된다.
각각의 노드들은 자신이 담당하는 구간의 연산값을 저장한다.
예를 들어 위 그림의 S4는 S8과 S9를 연산한 값이 저장된다.
리프 노드가 업데이트되면 자신을 포함하는 부모 노드를 차례대로 찾아올라가며 노드 값을 업데이트 한다.
구간 간의 연산값을 구할 때는 구하는 구간에 포함되는 가장 큰 구간 덩어리들을 합쳐 연산한다.
업데이트와 구간 연산을 그림으로 나타내면 아래와 같다.
S10 노드를 업데이트한 예시이다. S10은 S5의 자식이고 S5는 S2의 자식이고 S2는 S1의 자식이므로 S10을 변경하면 S5, S2, S1이 모두 영향을 받는다. 따라서 해당 구간들을 모두 업데이트 해야 하고 이 때 이진 트리의 계층 수 만큼의 연산이 발생하므로 각 노드의 업데이트가 O(1)이라면 총 시간 복잡도는 O(logN)이 된다.
![[Pasted image 20240812163058.png|S9S14 연산값 구하기]]
그 다음은 특정 구간의 최적값을 구하는 예시이다. 구해야 하는 전체 구간에 포함되는 노드를 탐색하고 연산한다. 이 때도 마찬가지로 현재 검사하는 구간이 전체 구간에 포함되는지 여부로 이진 탐색을 하게 되므로 시간 복잡도는 O(logN)이 된다.
위의 그림은 S9S14 구간의 연산을 구할 때 더해지는 노드를 표시한 것이다.
2. 구간합 세그먼트 트리 구현
N개의 수가 주어질 때 아래 2가지 쿼리에 대해 답을 출력할 수 있는 세그먼트 트리를 직접 만들어보자.
배열의 특정 인덱스 N에 있는 값을 P로 바꾸기 ( P는 음수일 수 있음 )
입력은 1 N P로 주어짐
배열의 특정 구간 S~E의 합 계산하기
입력은 2 S E 로 주어짐
먼저 가장 처음 주어지는 배열로 세그먼트 트리를 초기화부터 해보자.
세그먼트 트리는 이진 트리 구조이므로 필요한 배열의 크기는 2⌈log2N⌉+1−1이 된다.
재귀 호출을 사용해 자식 노드 2개의 합을 구하고 그 값을 부모 노드에 저장하는 과정을 반복한다.
코드는 아래와 같다.
#include <iostream>#include <algorithm>#include <vector>using namespace std;int n;vector<int> arr, seg;// n : tree 기준 노드 번호// s : 배열 구간 시작 인덱스// e : 배열 구간 종료 종료 인덱스int init(int n, int s, int e) { if (s == e) { // 시작 인덱스와 종료 인덱스가 같다면 리프 노드이므로 배열값 반환 return seg[n] = arr[s]; } int mid = (s + e) / 2; int s1 = init(n * 2, s, mid); // 왼자식 탐색 int s2 = init(n * 2 + 1, mid + 1, e); // 오른자식 탐색 return seg[n] = s1 + s2; // 양쪽 자식 합친 값 반환}int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; arr = vector<int>(n + 1); seg = vector<int>((int)pow(2, (int)ceil(log2(n)) + 1)); for (int i = 1; i <= n; i++) { cin >> arr[i]; } init(1, 1, n); return 0;}
이 코드에 아래 입력을 넣고 seg 배열값을 관찰해보자.
5
1 2 3 4 5
아래와 같은 결과가 나올 것이다.
15 6 9 3 3 4 5 1 2
이 결과를 그림으로 나타내면 아래와 같다.
원하는대로 잘 초기화 된 세그먼트 트리 배열을 획득했다.
다음은 특정 인덱스를 업데이트하는 함수를 작성해보자.
변경 대상인 리프 노드를 탐색하고 업데이트한 뒤, 노드의 변화량을 리턴한다.
그 후 부모 노드들도 모두 변화량만큼 업데이트를 해준다.
만약 탐색한 구간이 변경 대상 인덱스를 포함하지 않는 경우 변화량 0을 리턴한다.
코드는 아래와 같다.
#include <iostream>#include <algorithm>#include <vector>using namespace std;int n;vector<int> arr, seg;// n : tree 기준 노드 번호// s : 배열 구간 시작 인덱스// e : 배열 구간 종료 종료 인덱스int init(int n, int s, int e) { if (s == e) { // 시작 인덱스와 종료 인덱스가 같다면 리프 노드이므로 배열값 반환 return seg[n] = arr[s]; } int mid = (s + e) / 2; int s1 = init(n * 2, s, mid); // 왼자식 탐색 int s2 = init(n * 2 + 1, mid + 1, e); // 오른자식 탐색 return seg[n] = s1 + s2; // 양쪽 자식 합친 값 반환}// n : tree 기준 노드 번호// t : 업데이트 대상 인덱스// p : 업데이트 값// s : 배열 구간 시작 인덱스// e : 배열 구간 종료 종료 인덱스 int update(int n, int t, int p, int s, int e) { if (t < s || t > e) return 0; // 구간이 업데이트 대상 인덱스를 포함하지 않으면 변화량 0 if (s == e) { // 업데이트 대상 리프 노드를 찾으면 int tmp = seg[n]; seg[n] = p; return p - tmp; // 해당 노드의 변화량 반환 } int mid = (s + e) / 2; int s1 = update(n * 2, t, p, s, mid); // 왼자식 탐색 int s2 = update(n * 2 + 1, t, p, mid + 1, e); // 오른자식 탐색 seg[n] += s1 + s2; // 자식의 변화량 만큼 부모도 업데이트 return s1 + s2; // 변화량 반환}int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; arr = vector<int>(n + 1); seg = vector<int>((int)pow(2, (int)ceil(log2(n)) + 1)); for (int i = 1; i <= n; i++) { cin >> arr[i]; } init(1, 1, n); update(1, 1, 5, 1, n); return 0;}
이전 예제를 그대로 입력하고 세그먼트 트리가 어떻게 변하는지 살펴보자.
아래와 같은 결과가 나올 것이다.
19 10 9 7 3 4 5 5 2
그림으로 나타내면 아래와 같다.
업데이트도 정상적으로 잘되는 것을 확인할 수 있다.
마지막으로 특정 구간의 합을 계산하는 코드를 작성해보자.
현재 구간이 대상 구간에 완전히 포함되는지 검사해 포함된다면 노드 값을 리턴, 전혀 포함되지 않는다면 0을 리턴, 걸친다면 자식 노드 검사를 통해 합을 구할 수 있다.
코드는 아래와 같다.
#include <iostream>#include <algorithm>#include <vector>using namespace std;int n;vector<int> arr, seg;// n : tree 기준 노드 번호// s : 배열 구간 시작 인덱스// e : 배열 구간 종료 종료 인덱스int init(int n, int s, int e) { if (s == e) { // 시작 인덱스와 종료 인덱스가 같다면 리프 노드이므로 배열값 반환 return seg[n] = arr[s]; } int mid = (s + e) / 2; int s1 = init(n * 2, s, mid); // 왼자식 탐색 int s2 = init(n * 2 + 1, mid + 1, e); // 오른자식 탐색 return seg[n] = s1 + s2; // 양쪽 자식 합친 값 반환}// n : tree 기준 노드 번호// t : 업데이트 대상 인덱스// p : 업데이트 값// s : 배열 구간 시작 인덱스// e : 배열 구간 종료 종료 인덱스 int update(int n, int t, int p, int s, int e) { if (t < s || t > e) return 0; // 구간이 업데이트 대상 인덱스를 포함하지 않으면 변화량 0 if (s == e) { // 업데이트 대상 리프 노드를 찾으면 int tmp = seg[n]; seg[n] = p; return p - tmp; // 해당 노드의 변화량 반환 } int mid = (s + e) / 2; int s1 = update(n * 2, t, p, s, mid); // 왼자식 탐색 int s2 = update(n * 2 + 1, t, p, mid + 1, e); // 오른자식 탐색 seg[n] += s1 + s2; // 자식의 변화량 만큼 부모도 업데이트 return s1 + s2; // 변화량 반환}// n : tree 기준 노드 번호// l : 합을 구하는 구간 시작 인덱스// r : 합을 구하는 구간 종료 인덱스// s : 배열 구간 시작 인덱스// e : 배열 구간 종료 종료 인덱스 int getsum(int n, int l, int r, int s, int e) { if (l <= s && e <= r) return seg[n]; // 구간을 완전히 포함하는 경우, 노드 값 반환 if (r < s || e < l) return 0; // 구간이 전혀 포함되지 않는 경우, 탐색 중지 int mid = (s + e) / 2; int s1 = getsum(n * 2, l, r, s, mid); // 왼자식 탐색 int s2 = getsum(n * 2 + 1, l, r, mid + 1, e); // 오른자식 탐색 return s1 + s2; // 자식 합계 반환}int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; arr = vector<int>(n + 1); seg = vector<int>((int)pow(2, (int)ceil(log2(n)) + 1)); for (int i = 1; i <= n; i++) { cin >> arr[i]; } init(1, 1, n); update(1, 1, 5, 1, n); cout << getsum(1, 1, 4, 1, n); return 0;}
현재 인덱스 14까지의 합을 구하도록 되어있으므로 아래 그림에서 녹색 노드에 있는 값을 더하게 된다.
1번 노드의 구간은 15로 구간 14에 걸친다. 따라서 두 자식 노드 2, 3에 대해 추가 탐색을 진행한다.
2번 노드의 구간은 13으로 구간 14에 포함된다. 따라서 추가 탐색을 하지 않고 노드에 저장된 값 10을 반환한다.
3번 노드의 구간은 45로 구간 14에 걸친다. 따라서 두 자식노드 6, 7에 대해 추가 탐색을 진행한다.
6번 노드는 4번 배열인덱스에 대한 리프 노드이고 구간 14에 포함되므로 저장된 값 4를 반환한다.
7번 노드는 5번 배열인덱스에 대한 리프 노드이고 구간 1~4에 포함되지 않으므로 0을 반환한다.
따라서 최종 합계는 10+4=14가된다.
update함수와 getsum함수는 각각 O(logN)의 시간 복잡도를 가지므로 M개의 쿼리가 주어질 때의 최종 시간 복잡도는 O(MlogN)이 된다.
S10 노드를 업데이트한 예시이다. S10은 S5의 자식이고 S5는 S2의 자식이고 S2는 S1의 자식이므로 S10을 변경하면 S5, S2, S1이 모두 영향을 받는다. 따라서 해당 구간들을 모두 업데이트 해야 하고 이 때 이진 트리의 계층 수 만큼의 연산이 발생하므로 각 노드의 업데이트가 이라면 총 시간 복잡도는 이 된다.
원하는대로 잘 초기화 된 세그먼트 트리 배열을 획득했다.
업데이트도 정상적으로 잘되는 것을 확인할 수 있다.
1번 노드의 구간은 1