DAMPER's blog

세그먼트 트리 - (1). 기본 구조 본문

Problem Solving/Algorithms

세그먼트 트리 - (1). 기본 구조

DAMPER 2022. 5. 27. 02:40
728x90

PS분야에서 정말 다양하게 쓰이고 있는 자료구조로 자유자재로 쓰고싶은 마음에 이번 기회에 정리하고자 한다.

 

세그먼트 트리는 흔히 일차원 배열의 특정 구간에 대한 쿼리를 빠르게 답하는 데 사용한다.

물론 다차원 배열의 특정 구간에 대한 세그먼트 트리도 구현이 가능하다.

 

가장 기본적인 예로 어떤 배열의 부분 구간의 최소치를 구하는 연산을 여러번 하는 것이다.

배열 A = {1, 2, 1, 4, 6, 1, 5, 8}가 있다면 구간[2, 4]의 최소값은 1이고 구간[6, 7]의 최소값은 5이다.

이 문제를 세그먼트 트리를 통해 O(qlogn)에 해결할 수 있다.

 

세그먼트 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다.

루트는 전체 구간을 표현하고, 리프는 1개만을 표현한다.

 

왼쪽 자식과 오른쪽 자식은 각각 부모 구간의 왼쪽 반과 오른쪽 반을 표현한다.

예를 들어, 부모가 구간[0, N-1]을 표현한다면, 그 왼쪽 자식은 [0, (N-1)/2]를, 오른쪽 자식은[(N-1)/2+1, N-1]를 표현한다.

세그먼트 트리의 구간을 표현하면 다음과 같다.

이 때 세그먼트 트리는 노드마다 해당 구간에 대한 계산 결과를 저장해둔다.

위 예시 경우 구간의 최소값을 구하는 세그먼트 트리는 해당 구간의 최소값을 각 노드에 저장한다.

 

이렇게 전처리 과정을 수행해두면 어떤 구간 [i, j]가 주어지더라도 해당 구간을 세그먼트 트리의 노드에 포함된 구간들의 합집합으로 표현할 수 있다.

구간 [1, 4]인 경우 [1,1], [2,3], [4, 4] 이 3개의 연산 결과임을 알 수 있다.

어떤 구간이 주어지건 간에 O(logn)만에 찾아낼 수 있다.

 

 

다음 문제는 길이가 N인 수열에서 어떤 구간[i, j]에서 최솟값의 인덱스를 출력하는 문제이다.

 

 

https://www.acmicpc.net/problem/14428

 

14428번: 수열과 쿼리 16

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
 
vector<int> v;
vector<pii> seg_tree;
int tree_size, half_size, n;
 
void constr_tree()
{
    for(int i=0;i<n;i++)
    {
        seg_tree[i+half_size].first = v[i];
        seg_tree[i+half_size].second = i;
    }
    for(int i=half_size-1;i>0;i--)
    {
        seg_tree[i] = min(seg_tree[i*2], seg_tree[i*2+1]);
    }
}
 
void update(int nodeNum, int value)
{
    nodeNum += half_size;
    seg_tree[nodeNum].first = value;
    while(nodeNum > 1)
    {
        nodeNum >>= 1;
        seg_tree[nodeNum] = min(seg_tree[nodeNum*2], seg_tree[nodeNum*2+1]);
    }
}
 
pii get_seg_cal(int FL, int FR, int nodeNum, int left, int right)
{
    if(FL > right || FR < left) return {INT_MAX, INT_MAX};
    if(FL <= left && right <= FR)
    {
        return seg_tree[nodeNum];
    }
    int mid = (left+right)/2;
    return min(get_seg_cal(FL, FR, nodeNum*2, left, mid), 
get_seg_cal(FL, FR, nodeNum*2+1, mid+1, right));
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    v.resize(n, 0);
    for(int i=0;i<n;i++)
    {
        cin >> v[i];
    }
    int depth = (int)ceil(log2(n))+1;
    tree_size = 1 << depth + 1;
    half_size = tree_size >> 1;
    seg_tree.resize(tree_size, {INT_MAX, INT_MAX});
 
    constr_tree();
 
    int q, a, b, c;
    cin >> q;
    while(q-- > 0)
    {
        cin >> a >> b >> c;
        if(a == 1)
        {
            update(b-1, c);
        }
        else
        {
            pii tmp = get_seg_cal(b-1, c-1, 1, 0, half_size-1);
            cout << tmp.second+1 << endl;
        }
    }
 
    return 0;
}
 cs
 
 
  

 

 

728x90

'Problem Solving > Algorithms' 카테고리의 다른 글

알고리즘과 효율성 분석  (0) 2023.02.14
세그먼트 트리 - (3). K번째 원소 찾기  (0) 2022.07.03
세그먼트 트리 - (2). Counting Inversions  (0) 2022.05.28
'Problem Solving/Algorithms' Related Articles more