�ݺ�ߣ

Segment Tree
(세그먼트 트리)
1. Top-Down
2022.08.02 김봄

Segment Tree (세그먼트 트리)
Segment Tree는 배열의 구간 연산을 빠르게 계산할 수 있다.
시간복잡도: 𝑂𝑂(log2 𝑁𝑁)
(구간 합, 구간 곱, 구간 최소값, 구간 최대값)
9 5 1 4 8 3 6 9
14 5 11 15
19 26
45
2 7
45 19 26 14 5 11 15 9 5 1 4 8 3 6 9 2 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Segment Tree 도식화
(위 그림처럼 인접한 쌍의 합을 만든다)
Segment Tree 실제 구현
(위의 트리모양 도식화를 배열로 구현한 것이다)
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
입력 배열

Segment Tree 생성
입력 배열의 크기가 N일때 Segment Tree의 크기는 2N-1이다.
Segment Tree 배열의 크기
입력 배열 크기: 2
▼
필요 배열 크기: 3
▼
▼
▼
▼
▼
▼
▼
45 19 26 14 5 11 15 9 5 1 4 8 3 6 9 2 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
입력 배열 Segment Tree
입력 배열의 크기가 N일때 N-1부터 리프노드를 채울 수 있다.
(입력 배열이 9개이므로 Index 8부터 리프노드로 채울 수 있다.)
Segment Tree 리프노드 채우기

Segment Tree 생성
Segment Tree 리프노드 순서에 맞게 채우기
9 5 1 4 8 3 6 9
14 5 11 15
19 26
45
2 7
45 19 26 14 5 11 15 9 5 1 4 8 3 6 9 2 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
리프노드(입력 배열)의 깊이(depth)가 다를 수 있다.
다른 경우에는 가장 아래 원소를 먼저 채워준다.
2 log2 2𝑁𝑁−1
− 1 pow(2, floor(log2(2*N-1))) - 1
위의 위치부터 Segment Tree의 끝까지 채우고,
(C/C++ code)
N-1 부터 나머지를 채우면 된다.
Segment Tree 나머지 구간 채우기
특정 Index를 기준으로,
Left Child Index과 Right Child Index는 아래의 수식으로 구할 수 있다.
𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 = 2 𝑖𝑖 + 1 − 1
𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 = 2 𝑖𝑖 + 1
N-2 부터 0 까지 해당 Index의 Left Node와 Right Node를 더해서 저장한다.
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
입력 배열

Segment Tree 생성
Python/C++ Code
from typing import List
import math
def make_stree(arr: List) -> List:
stree_size = len(arr) * 2 - 1
stree = [0] * stree_size
j = 2 ** math.floor(math.log2(stree_size)) - 1
i = 0
while i != len(arr):
stree[j] = arr[i]
j += 1
i += 1
if j == len(stree):
j = len(arr) - 1
for k in reversed(range(0, len(arr) - 1)):
left = (k + 1) * 2 - 1
right = (k + 1) * 2
stree[k] = stree[left] + stree[right]
return stree
arr = [2, 7, 5, 1, 4, 8, 3, 6, 9]
stree = make_stree(arr)
print(stree)
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
using lld = long long;
vector<lld> make_stree(const vector<lld> &arr) {
vector<lld> stree(arr.size() * 2 - 1, 0);
int j = pow(2, floor(log2(stree.size()))) - 1;
int i = 0;
while (i != arr.size()) {
stree[j++] = arr[i++];
if (j == stree.size()) {
j = arr.size() - 1;
}
}
for (int k = arr.size() - 2; k >= 0; k--) {
int left = (k + 1) * 2 - 1;
int right = (k + 1) * 2;
stree[k] = stree[left] + stree[right];
}
return stree;
}
int main() {
vector<lld> A = {2, 7, 5, 1, 4, 8, 3, 6, 9};
vector<lld> stree = make_stree(A);
for (auto &e : stree) {
cout << e << ", ";
}
cout << endl;
return 0;
}
Python
C++

Segment Tree 연산
Non recursive
9 5 1 4 8 3 6 9
14 5 11 15
19 26
45
2 7
3번째 부터 7번째 까지의 구간 합을 구하고 싶다면 아래 그림에서는 빨간색 노드의 합을 구하면 된다.
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
입력 배열

Segment Tree 연산
완전이진트리에서 루트노드를 기준으로 왼쪽, 오른쪽 자식의 개수는 절반이 아니다.
Segment Tree 오른쪽 자식의 개수
왼쪽 자식 개수:1
오른쪽 자식 개수:1
데이터
개수
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
왼쪽
개수
1 2 2 3 4 4 4 5 6 7 8 8 8 8 8 9
오른쪽
개수
1 1 2 2 2 3 4 4 4 4 4 5 6 7 8 8
𝑓𝑓 𝑛𝑛 = �𝑛𝑛 −
𝑘𝑘
2
, 𝑖𝑖𝑖𝑖 𝑛𝑛 ≤
𝑘𝑘 + 2𝑘𝑘
2
𝑛𝑛 − 𝑘𝑘, 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜
, 𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤: 𝑘𝑘 = 2 log2 𝑛𝑛
, 𝑛𝑛 𝑖𝑖𝑖𝑖 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
𝑔𝑔 𝑛𝑛 = min 𝑓𝑓 𝑛𝑛 , 𝑛𝑛 − 𝑓𝑓 𝑛𝑛
위 수식으로 오른쪽 자식의 개수를 구할 수 있다.

Segment Tree 연산
Non recursive
9 5 1 4 8 3 6 9
14 5 11 15
19 26
45
2 7
[0,8]
계산하고자 하는 (1)구간에 포함되면 더하고, (2)겹치면 분할하고, (3)포함되지 않으면 계산하지 않는다.
[0,8]은 [2,6]에 포함되지 않는다.
[0,4], [5,8] 구간으로 나누어서 계산한다.
0 8
6
2
루트 노드의 범위는 [0,N-1]에서 시작한다.
왼쪽 자식 노드의 범위는 [부모 노드의 시작 구간,부모 노드 구간의 중간]
오른쪽 자식 노드의 범위는[부모 노드 구간의 중간+1,부모 노드의 끝 구간]

Segment Tree 연산
Non recursive
9 5 1 4 8 3 6 9
14 5 11 15
19 26
45
2 7
[0,8]
[0,4]은 [2,6]에 포함되지 않는다.
[0,2], [3,4] 구간으로 나누어서 계산한다. [0,4] [5,8]
[5,8]은 [2,6]에 포함되지 않는다.
[5,6], [7,8] 구간으로 나누어서 계산한다.
그런데 [7,8]은 [2,6]과 겹치는 구간이 없다.
따라서, [7,8]은 계산하지 않는다.
0 4
6
2
5 8

Segment Tree 연산
Non recursive
9 5 1 4 8 3 6 9
14 5 11 15
19 26
45
2 7
[0,8]
[3,4]은 [2,6]에 포함된다! [0,4] [5,8] [5,6]은 [2,6]에 포함된다!
3 4
6
2
5
[3,4]
[0,2]
[0,2]은 [2,6]에 포함되지 않는다.
[0,1], [2] 구간으로 나누어서 계산한다.
그런데 [0,1]은 [2,6]과 겹치지 않으므로,
계산하지 않는다.
0 2 6

Segment Tree 연산
Non recursive
9 5 1 4 8 3 6 9
14 5 11 15
19 26
45
2 7
[0,8]
[2]은 [2,6]에 포함된다! [0,4] [5,8]
6
2
[3,4]
[0,2]
2
[2]

Segment Tree 연산
Python/C++ Code
def calc_stree(stree: List, L: int, R: int):
length = (len(stree) + 1) // 2
ret = 0
q = [(0, 0, length - 1)]
while len(q) != 0:
idx, left, right = q[0]
q = q[1:]
if L <= left and right <= R:
ret += stree[idx]
else:
left_idx = (idx + 1) * 2 - 1
right_idx = (idx + 1) * 2
n = right - left + 1
k = 2 ** math.floor(math.log2(n))
other = n - k // 2 if n <= (k + k * 2) // 2 else n - k
right_cnt = min(other, n - other)
mid = right - right_cnt
if L <= mid:
q.append((left_idx, left, mid))
if mid + 1 <= R:
q.append((right_idx, mid + 1, right))
return ret
lld calc_stree(const vector<lld>& stree, const int L, const int R) {
const lld length = (stree.size() + 1) / 2;
lld ret = 0;
queue<tuple<lld, lld, lld>> q;
q.push(make_tuple(0, 0, length - 1));
while (!q.empty()) {
lld idx, left, right;
std::tie(idx, left, right) = q.front();
q.pop();
if (L <= left && right <= R) {
ret += stree[idx];
}
else {
int left_idx = (idx + 1) * 2 - 1;
int right_idx = (idx + 1) * 2;
int n = right - left+1;
int k = (int)pow(2, floor(log2(n)));
int other = (n <= (k + k * 2) / 2) ? n - k / 2 : n - k;
int right_cnt = min(other, n - other);
int mid = right - right_cnt;
if (L <= mid) {
q.push(make_tuple(left_idx, left, mid));
}
if (mid + 1 <= R) {
q.push(make_tuple(right_idx, mid + 1, right));
}
}
}
return ret;
}
Python
C++

Segment Tree 업데이트
수정하려는 리프노드의 Index 구하기
입력 배열의 0번째 Index를 Segment Tree에서 찾은 후,
수정하려는 곳의 Index 만큼 더해준다.
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 = �
− 1 + 𝑖𝑖𝑖𝑖𝑖𝑖, 𝑖𝑖𝑖𝑖 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 < 2𝑁𝑁 − 1
− 1 + 𝑖𝑖𝑖𝑖𝑖𝑖 − 𝑁𝑁, 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜
해당 Leaf Node 부터 Root Node 까지 구간합 갱신하기
Parent Node Index는 아래의 수식으로 구할 수 있다.
𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝_𝑖𝑖𝑖𝑖𝑖𝑖 =
𝑖𝑖 − 1
2
Leaf Node의 Parent Node 부터 Root Node 까지 Left Node와 Right Node의 합을 갱신하면 된다.
리프노드의 깊이가 다를때를 고려하여 아래 수식으로 계산할 수 있다.
9 5 3 4 8 3 6 9
14 7 11 15
21 26
47
2 7
45 19 26 14 5 11 15 9 5 1 4 8 3 6 9 2 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
47 21 26 14 7 11 15 9 5 3 4 8 3 6 9 2 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
2 7 5 3 4 8 3 6 9
0 1 2 3 4 5 6 7 8
기존 배열의 4번째 값1을 3으로 변경하는 예시
(기존 배열에서 변경하는게 아니라, Segment Tree에서 변경한다.)

Python/C++ Code
void update_stree(vector<lld>& stree, lld idx, lld data) {
const lld length = (stree.size() + 1) / 2;
lld sidx = pow(2, floor(log2(stree.size()))) - 1 + idx;
if (sidx >= stree.size()) {
sidx -= length;
}
stree[sidx] = data;
while (sidx != 0) {
sidx = (sidx - 1) / 2;
lld left = (sidx + 1) * 2 - 1;
lld right = (sidx + 1) * 2;
stree[sidx] = stree[left] + stree[right];
}
}
C++
def update_stree(stree: List, idx: int, data):
length = (len(stree) + 1) // 2
sidx = 2 ** math.floor(math.log2(len(stree))) – 1 + idx
if sidx >= len(stree):
sidx -= length
stree[sidx] = data
while sidx != 0:
sidx = (sidx – 1) // 2
left = (sidx + 1) * 2 – 1
right = (sidx + 1) * 2
stree[sidx] = stree[left] + stree[right]
Python

Segment Tree
(세그먼트 트리)
2. Bottom-Up

Segment Tree 생성
입력 배열의 크기가 N일때 Segment Tree의 크기는 2N-1이다.
Segment Tree 배열의 크기
▼
▼
▼
▼
▼
▼
▼
▼
0 45 29 16 17 12 5 11 15 2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
입력 배열 Segment Tree
입력 배열의 크기가 N일때 N부터 리프노드를 채울 수 있다.
(0번째 Index는 사용하지 않는다, 따라서 Segment Tree의 크기를 2N으로 초기화)
(입력 배열이 9개이므로 Index 9부터 리프노드로 채울 수 있다.)
Segment Tree 리프노드 채우기

Segment Tree 생성
Segment Tree 리프노드 순서에 맞게 채우기
15 2 7 5 1 4 8 3
17 12 5 11
29 16
45
6 9
리프노드(입력 배열)의 깊이(depth)가 다른 것과 상관 없이
N 부터 차례대로 채워준다.
Segment Tree 나머지 구간 채우기
특정 Index를 기준으로,
Left Child Index과 Right Child Index는 아래의 수식으로 구할 수 있다.
𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 = 2𝑖𝑖
𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 = 2𝑖𝑖 + 1
N-1부터 1 까지 해당 Index의 Left Node와 Right Node를 더해서 저장한다.
0 45 29 16 17 12 5 11 15 2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
입력 배열

Segment Tree 생성
Python/C++ Code
from typing import List
def make_stree(arr: List) -> List:
stree_size = len(arr) * 2
stree = [0] * stree_size
j = len(arr)
i = 0
while i != len(arr):
stree[j] = arr[i]
j += 1
i += 1
for k in reversed(range(1, len(arr))):
stree[k] = stree[2 * k] + stree[2 * k + 1]
return stree
arr = [2, 7, 5, 1, 4, 8, 3, 6, 9]
stree = make_stree(arr)
print(stree)
#include<iostream>
#include<vector>
using namespace std;
using lld = long long;
vector<lld> make_stree(const vector<lld> &arr) {
vector<lld> stree(arr.size() * 2, 0);
int j = arr.size();
int i = 0;
while (i != arr.size()) {
stree[j++] = arr[i++];
}
for (int k = arr.size() - 1; k > 0; k--) {
stree[k] = stree[2 * k] + stree[2 * k + 1];
}
return stree;
}
int main() {
vector<lld> A = {2, 7, 5, 1, 4, 8, 3, 6, 9};
vector<lld> stree = make_stree(A);
for (auto &e : stree) {
cout << e << ", ";
}
cout << endl;
return 0;
}
Python
C++

Segment Tree 연산
Non recursive
15 2 7 5 1 4 8 3
17 12 5 11
29 16
45
6 9
3번째 부터 7번째 까지의 구간 합을 구하고 싶다면 아래 그림에서는 빨간색 노드의 합을 구하면 된다.
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
입력 배열

Segment Tree 연산
Non recursive
구간의 왼쪽 원소 : (1)오른쪽 자식이면 더하고 Index를 오른쪽으로 한 칸 이동, (2)왼쪽 자식이면 부모 노드로 올라간다.
구간의 오른쪽 원소 : (1)왼쪽 자식이면 더하고 Index를 왼쪽으로 한 칸 이동, (2)오른쪽 자식이면 부모 노드로 올라간다.
15 2 7 5 1 4 8 3
17 12 5 11
29 16
45
6 9
구간의 왼쪽 원소와 오른쪽 원소에 따라 다른 이유
구해야 하는 값이 구간의 왼쪽 원소와 오른쪽 원소 사이 값들의 합이기 때문에
왼쪽 원소일 때는 오른쪽 자식이면 부모 노드로 올라갈 수 없다.
(부모 노드는 왼쪽 자식과 오른쪽 자식의 합)
따라서 해당 값을 더하고, Index를 오른쪽으로 한 칸 이동한 후
부모 노드로 올라간다.
오른쪽 원소일 때는 왼쪽 자식이면 부모 노드로 올라갈 수 없다.
(부모 노드는 왼쪽 자식과 오른쪽 자식의 합)
따라서 해당 값을 더하고, Index를 왼쪽으로 한 칸 이동한 후
6
2
왼쪽 원소 오른쪽 원소

Segment Tree 연산
Non recursive
15 2 7 5 1 4 8 3
17 12 5 11
29 16
45
6 9
왼쪽 자식인지 오른쪽 자식인지 판단하는 방법
왼쪽 자식 : Index가 짝수, 오른쪽 자식 : Index가 홀수
부모 노드로 올라가는 식
Index = Index / 2
6
2
왼쪽 원소 오른쪽 원소
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17

Segment Tree 연산
Non recursive
6
2
15 2 7 5 1 4 8 3
17 12 5 11
29 16
45
6 9
5는 오른쪽 자식이기 때문에
부모 노드로 올라갈 수 없다.
따라서 5를 더한다.
그 후에 오른쪽으로 한 칸 이동하고
3은 오른쪽 자식이기 때문에
부모 노드로 올라갈 수 있다.
따라서 더하지 않고 부모 노드로 올라간다.

Segment Tree 연산
Non recursive
6
2
15 2 7 5 1 4 8 3
17 12 5 11
29 16
45
6 9
5는 왼쪽 자식이기 때문에
11은 오른쪽 자식이기 때문에

Segment Tree 연산
Non recursive
6
2
15 2 7 5 1 4 8 3
17 12 5 11
29 16
45
6 9
16은 오른쪽 자식이다.
왼쪽 원소 기준으로는 오른쪽 자식이면
더해야 하므로 16을 더한다.
오른쪽 원소 기준으로는 오른쪽 자식이면
부모 노드로 올라가야 하지만
왼쪽 원소와 오른쪽 원소가 만났기 때문에 마친다.

Segment Tree 연산
Python/C++ Code
def calc_stree(stree: List, L: int, R: int):
length = len(stree) // 2
ret = 0
left = L – 1 + length
right = R – 1 + length
while left <= right:
if left % 2 == 1:
ret += stree[left]
left += 1
if right % 2 == 0:
ret += stree[right]
right -= 1
left //= 2
right //= 2
return ret
lld calc_stree(const vector<lld>& stree, const int L, const int R) {
const lld length = stree.size() / 2;
lld ret = 0;
lld left = L – 1 + length;
lld right = R – 1 + length;
for (left, right; left <= right; left /= 2, right /= 2) {
if (left % 2 == 1) {
ret += stree[left];
left++;
}
if (right % 2 == 0) {
ret += stree[right];
right--;
}
}
return ret;
}
Python
C++

수정하려는 리프노드의 Index 구하기
입력 배열의 0번째 Index를 Segment Tree에서 찾은 후,
수정하려는 곳의 Index 만큼 더해준다.
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 = 𝑁𝑁 + 𝑖𝑖𝑖𝑖𝑖𝑖 − 1
해당 Leaf Node 부터 Root Node 까지 구간합 갱신하기
Parent Node Index는 아래의 수식으로 구할 수 있다.
𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝_𝑖𝑖𝑖𝑖𝑖𝑖 =
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
2
Leaf Node의 Parent Node 부터 Root Node 까지 Left Node와 Right Node의 합을 갱신하면 된다.
15 2 7 5 3 4 8 3
17 12 7 11
29 18
47
6 9
2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8
2 7 5 3 4 8 3 6 9
0 1 2 3 4 5 6 7 8
기존 배열의 4번째 값1을 3으로 변경하는 예시
(기존 배열에서 변경하는게 아니라, Segment Tree에서 변경한다.)
0 45 29 16 17 12 5 11 15 2 7 5 1 4 8 3 6 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 47 29 18 17 12 7 11 15 2 7 5 3 4 8 3 6 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
sidx가 짝수일 때 - Left Node Index : sidx, Right Node Index : sidx + 1
sidx가 홀수일 때 - Left Node Index : sidx – 1, Right Node Index : sidx

Python/C++ Code
void update_stree(vector<lld>& stree, lld idx, lld data) {
const lld length = stree.size() / 2;
lld sidx = length + idx - 1;
for (stree[sidx] = data; sidx > 1; sidx /= 2) {
if (sidx % 2 == 0) {
stree[sidx / 2] = stree[sidx] + stree[sidx + 1];
}
else {
stree[sidx / 2] = stree[sidx] + stree[sidx – 1];
}
}
}
C++
def update_stree(stree: List, idx: int, data):
length = len(stree) // 2
sidx = length + idx - 1
stree[sidx] = data
while sidx > 1:
if sidx % 2 == 0:
stree[sidx // 2] = stree[sidx] + stree[sidx + 1]
else:
stree[sidx // 2] = stree[sidx] + stree[sidx – 1]
sidx //= 2
Python

�ݺ�ߣ

SegmentTree Datastructure description and implementation slides

Recommended

More Related Content

Similar to SegmentTree Datastructure description and implementation slides (20)

More from Bomm Kim (6)

SegmentTree Datastructure description and implementation slides