세그먼트 트리는 data를 구간별로 나누고 작업해야 하는 과정 중
구간별로 나누어 반복적으로 실행할 작업들의 결과를 미리 계산하여 저장해 둔 트라이입니다.
이후 해당 작업을 수행하는 대신 세그먼트 트리 내에 있는 결과를 통해 보다 빠르게 원하는 결괏값을 받아올 수 있습니다.
세그먼트 트리는 바이너리 트리로 구성되어 있다.
data의 시작 index를 0 마지막 index를 9라고 가정하면 루트는 0~9의 구간을 나타내고
왼쪽의 자식 노드는 0~4 오른쪽 자식 노드는 5~9의 구간을 가지게 된다.
즉 부모노드 구간의 ( 시작 index + 마지막 index ) / 2를 기점으로 자식노드를 나누게 된다.
leaf 노드는 시작 index와 마지막 index가 같은 node들로 data의 개수만큼 존재하게 된다.
따라서, 세그먼트 트리의 자료구조의 높이(h)는 log2(n)이고
구현하기 위해서는 2^(h+1)-1만큼의 공간을 필요로 한다.
세그먼트 트리를 구현해 보도록 하겠습니다.
세그먼트 트리 내부에 들어가는 값은 가장 많이 사용하는 '구간 합'으로 하겠습니다.
long long seg_init(vector<long long> &data, vector<long long> &seg_T, long long begin, long long end, long long cur)
{
if (begin == end)
{
return seg_T[cur] = begin;
}
long long mid = (begin + end) / 2;
return seg_T[cur] = seg_init(data, seg_T, begin, mid, cur * 2 + 1) + seg_init(data, seg_T, mid + 1, end, cur * 2 + 2);
}재귀함수를 이용한다면 세그먼트 트리의 값들을 쉽게 초기화해 줄 수 있습니다.
재귀 함수에 필수적으로 구현해하는 종결조건은 begin과 end가 같을 때로 이는 앞서 설명한 leaf node를 나타내며
해당 leaf node는 data 그대로의 값을 의미합니다.
위 와 같은 방식의 코드로 seg_T에 세그먼트 트리의 값들을 초기화시킬 수 있습니다.
세그먼트 트리 값 초기화의 시간복잡도는 O(2^(h+1))입니다.
다음으로는 세그먼트 트리에 저장되어 있는 값들을 통해 구간별 합을 찾기 위한 함수입니다.
long long find_min(vector<long long> &data, vector<long long> &seg_T, long long begin, long long end, const long long find_s, const long long find_e, long long cur)
{
if (end < find_s || begin > find_e)
return 0;
if (find_s <= begin && end <= find_e)
return seg_T[cur];
long long mid = (begin + end) / 2;
return find_min(data, seg_T, begin, mid, find_s, find_e, cur * 2 + 1) +find_min(data, seg_T, mid + 1, end, find_s, find_e, cur * 2 + 2)
}구간 합을 찾을 때 사용되는 값은
1. 찾고자 하는 구간의 시작: find_s
2. 찾고자 하는 구간의 끝: find_e
3. 현재 세그먼트 트리 노드가 나타내는 구간의 시작: begin
4. 현재 세그먼트 트리 노드가 나타내는 구간의 끝: end
총 4가지를 비교하여 값을 return 해주게 됩니다.
find_s 가 end 보다 크거나 begin이 find_e보다 클 경우
현재 세그먼트 트리가 찾고자 하는 구간을 벗어난 경우이므로 0을 return 해줍니다.
만약 find_s가 begin보다 작고 end가 find_e보다 작을 경우
현재 세그먼트 트리가 찾고자 하는 구간 안에 있으므로 해당 노드의 값을 return 해 줍니다.
만일 두 가지 경우에 해당되지 않을 경우
자식노드를 찾도록 함수를 호출해 주고 두 함수에서 나온 값의 합을 return 해 줍니다.
위와 같은 과정을 통해서 원하는 구간의 합을 찾아낼 수 있습니다.
부모노드에서부터 leaf노드까지의 호출만을 요구하므로
세그먼트 트리의 값 검색의 시간복잡도는 O(h)입니다.
다음으로는 세그먼트 트리에 저장되어 있는 값을 변경하기 위한 함수입니다.
세그먼트 트리의 기반이 되는 data 값에 변화가 생길 경우에 사용되며
세그먼트 트리의 전부를 바꾸는 것이 아닌 바뀐 data에 영향을 받는 node만을 변경시켜
보다 적은 계산을 통해 시간적 효율적을 향상할 수 있게 됩니다.
void update(vector<long long> &seg_T, int node, int start, int end, int index, long long diff)
{
if (index < start || index > end)
return;
seg_T[node] = seg_T[node] + diff;
if (start != end)
{
update(seg_T, node*2, start, (start+end)/2, index, diff);
update(seg_T, node*2+1, (start+end)/2+1, end, index, diff);
}
}함수에 들어가는 parmeter들 중 diff와 index는 각각
diff: 변경된 data의 이전값과의 차이 값
index: 변경된 data의 index
를 의미합니다.
만약 index가 현재 node의 구간 안에 들어와 있지 않을 경우 재귀를 종결하도록 합니다.
현재 node의 구간 안에 들어와 있을 경우 diff만큼 node의 값을 변경시켜 주고
leaf노드가 아닐 경우 자식 node들의 값도 변경시켜 주도록 합니다.
부모노드에서부터 leaf노드까지의 호출만을 요구하므로
세그먼트 트리의 값을 수정의 시간복잡도는 O(h)입니다.
세그먼트 트리를 사용해서 풀 어볼 수 있는 문제는
https://www.acmicpc.net/problem/6549
6549번: 히스토그램에서 가장 큰 직사각형
문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이
www.acmicpc.net
https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의
www.acmicpc.net
https://www.acmicpc.net/problem/10868
10868번: 최솟값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은
www.acmicpc.net
https://www.acmicpc.net/problem/2357
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을
www.acmicpc.net
등이 있습니다.
'Computer Science > 자료구조' 카테고리의 다른 글
| Set 자료구조 비교 (c++, python) (0) | 2021.03.24 |
|---|
