세그먼트 트리와 모노이드

3월 22일 학회 스터디에서 작성했던 자료를 조금 수정해 백업합니다. 정확하지 않은 내용이 있을 수 있습니다.

세그먼트 트리

세그먼트 트리는 특정한 조건을 만족하는 이항연산을 어떤 구간에서 빠르게 반복(iterate)할 수 있게 해주는 자료구조입니다. wikipedia: Iterated binary operation

세그먼트 트리를 활용하기 위해서는 각 원소 위에 정의된 이항연산이 결합법칙을 만족하고 항등원을 가져야 합니다. 대수학적으로 이런 구조를 모노이드라고 부릅니다.

모노이드

대표적으로 32비트 정수 위에서의 합을 생각해보면, 결합법칙을 만족하고 항등원 0이 존재하므로 모노이드입니다. 또 32비트 정수와 max를 생각해 봅시다. 수학에서의 무한한 정수와 최댓값 연산은 항등원을 가지지 않습니다. (이처럼 결합법칙만을 만족하고 항등원을 가지지 않는 경우 이는 반군, semigroup이라고 합니다.) 그러나 임의로 항등원을 정의하거나(양의 정수 집합에 초기값으로 -1을 주거나, 유효한 값인지 불리언 변수로 따로 표시해주는 것을 생각해봅시다.), 32비트 정수처럼 유한하여 INT_MIN과 같은 최솟값이 주어지는 경우 이는 모노이드가 됩니다. 모노이드의 더 많은 예시

반복 이항연산

$(A,+)$라는 모노이드와 $A$의 원소(자료형이 A라고 이해할 수도 있습니다.)로 이루어진 수열 $a$가 주어졌다고 합시다. (너무 추상적이라 헷갈리면 그냥 정수와 덧셈이라고 생각하셔도 좋습니다.) 그리고 수열의 어떤 구간에 이 연산을 반복하는 것을 시그마로 표현해봅시다.

$$\sum _{k=l}^{r}a[k]=a[l]+a[l+1]+a[l+2]+\cdots +a[r]$$

연산 $+$이 결합법칙을 만족한다는 것은 이러한 식을 순서대로 계산하지 않고 원하는 대로 쪼개 계산할 수 있다는 것을 뜻합니다. 세그먼트 트리는 이를 이용해 미리 특정 구간을 쪼개 계산해둠으로써 이러한 계산들을 빠르게 수행합니다.

가운데부터 둘둘로 쪼개면 균형잡힌 이진트리의 꼴이 됨을 상상할 수 있습니다. 깊이는 $\lceil lo{g}_{2}N\rceil$이 되겠네요.

구조

기본적인 세그먼트 트리는 값을 담는 어레이와 초기화, 갱신, 쿼리를 수행하는 세 함수로 구성됩니다.  

2진 트리는 1차원 어레이로 표현되곤 하는데, 방법은 다음과 같습니다.

• 루트를 1번 노드로 잡습니다.
• n번 노드의 왼쪽 자식은 2n, 오른쪽 자식은 2n+1로 잡습니다.

잘 생각해보면 재귀적으로 각 노드에 독립적인 번호가 할당됨을 알 수 있습니다. 앞서 트리의 깊이가 $\lceil lo{g}_{2}N\rceil$이라고 했으므로 노드에 할당되는 번호는 $2^{\lceil lo{g}_{2}N\rceil +1}<4N$을 넘지 않습니다. 따라서 어레이의 길이는 4N정도로 잡으면 충분합니다. 이 배열을 $seg[]$로, 각 노드가 담당하는 범위의 시작을 $s$, 끝을 $e$라고 하겠습니다. 범위를 ‘반씩 쪼갠다’는 말을 구체적으로 식으로 쓰면 다음과 같습니다.

$$\begin{gathered} \text{init}:s[1]\leftarrow 0,e[1]\leftarrow N-1 \\ \text{for any node number }n\text{ such that }s[n]\ne e[n]: \\ s[2n]\leftarrow s[n],e[2n]\leftarrow \lfloor (s[n]+e[n])/2\rfloor \\ s[2n+1]\leftarrow e[2n]+1,e[2n+1]\leftarrow e[n] \end{gathered}$$

$s[n]=e[n]$라는 것은 곧 n번 노드가 담당하는 범위가 한 칸이라 더 쪼갤 것이 없음을, 트리에서는 리프 노드임을 말합니다. 이제 트리에 저장될 값은 재귀적으로 다음과 같습니다.

$$seg[n]=\{\begin{array}{rcc}seg[2n]+seg[2n+1]& \text{if}& s[n]\ne e[n]\\ a[s[n]]& \text{if}& s[n]=e[n]\end{array}$$

결과적으로는

$$seg[n]=\sum _{k=s[n]}^{e[n]}a[k]$$

가 될 것입니다. 다만 s와 e는 구현할 때는 따로 저장되는것보다 함수에 매개변수로 전달되는 것이 일반적입니다.

본격적으로 함수를 작성해 봅시다.

class A {
        // 자료형 A의 구현. 정수처럼 이미 정의되어 있는 경우 필요 없습니다.
};
  
A operator+(A a, A b) {
        // A 위의 연산 + 구현. 마찬가지로 정수의 덧셈처럼 이미 정의된 경우 필요 없습니다.
}
 
A identity; // (A,+)의 항등원. 덧셈에서의 0의 역할을 합니다.
 
int N=1000; // 수열 a의 길이
A a[N];
A seg[4*N];
 
void init(int n, int s, int e) { // 노드 번호 n, n번 노드의 담당 구간 [s, e]
    if(s==e) seg[n]=a[s];
    else {
		init(2*n, s, (s+e)/2);
		init(2*n+1, (s+e)/2+1, e);
		seg[n]=seg[2*n]+seg[2*n+1];
	}
}
 
void update(int n, int s, int e, int t) { // t stands for target: 변경한 a 원소의 인덱스
	if(e<t or t<s) return;
	else if(s==e) seg[n]=a[s];
	else {
		update(2*n, s, (s+e)/2, t);
		update(2*n+1, (s+e)/2+1, e, t);
		seg[n]=seg[2*n]+seg[2*n+1];
	}
}
 
A query(int n, int s, int e, int l, int r) {
	if(e<l or r<s) return identity;
	else if(l<=s and e<=r) return seg[n];
	else {
		return query(2*n, s, (s+e)/2, l, r)
		+ query(2*n+1, (s+e)/2+1, e, l, r)
	}
}

세 함수의 조건분기가 비슷한 것을 볼 수 있습니다. 세 함수가 기본적으로 하는 일은 ”이 노드가 원하는 구간과 겹치지 않으면 스킵(혹은 항등원을 반환)하고, 구간에 포함되면 값을 반환하고, 걸친다면 더 잘게 쪼갠다” 입니다. init은 전구간, update는 특정 원소 t, query는 부분 구간 [l, r]이라는 점이 다르지만요. 앞의 두 함수는 값을 갱신하기만 하지만 쿼리는 실제로 값을 구해야 하기 때문에 값을 반환한다는 점도 다릅니다. +이 상수 시간에 처리된다고 가정하면, init은 세그트리의 모든 노드를 갱신하므로 $O(N)$ (앞서 보인 것과 같이 세그트리의 크기는 $4N$을 넘지 않습니다.), query는 균형 잡힌 이진트리에서 각 깊이에서 많아야 네개, update는 하나의 노드를 방문하므로 트리의 깊이에 비례해 $O(\log N)$의 시간복잡도를 가집니다. 부분 합의 경우 갱신에 $O(N)$, 쿼리에 $O(1)$이 걸리는 것과는 대조적입니다.

모노이드 설정하기

금광 세그라는 테크닉이 있습니다만 사실 조금 복잡한 모노이드를 어떻게 잘 설정해야 하는지에 관한 문제입니다.

16993번: 연속합과 쿼리

우선 단순 정수합으론 풀리지 않을 것 같습니다. 어떤 구간에서 구간합의 최대를 구한다면, 이 구간을 반으로 쪼갰을 때 각각의 반쪽에서 어떤 정보가 필요할까요?

• 최대 합을 가지는 구간이 쪼개지는 부분에 걸칠 수도 있고 왼쪽에 있을 수도 있고 오른쪽에 있을 수도 있습니다.
• 그렇다면 양 옆에서 최대 합과 왼쪽에서는 오른쪽에 붙은 최대, 오른쪽에서는 왼쪽에 붙은 최대를 붙이면 이 세 구간이 최대 합의 후보가 되겠네요.
• 그럼 한쪽에 붙은 최대의 후보는 어떤 걸까요? 왼쪽에 붙은 최대 합의 후보는 왼쪽 노드의 왼쪽 최대합과 왼쪽 전체+오른쪽 노드의 왼쪽 최대합이겠네요. 오른쪽 최대합은 반대로 하면 됩니다.
• 전체 합은 양쪽의 전체 합만으로 구할 수 있습니다.

따라서 최대합, 왼쪽 최대합, 오른쪽 최대합, 전체합 네가지 정보로 구성된 자료형 A와 위에 말한 대로 정의된 이항연산 +가 있으면 문제를 해결할 수 있습니다.

struct node {
    int l, r, n, a; // 왼쪽 최대합, 오른쪽 최대합, 전체 최대합, 전체 합
};
 
node operator +(node a, node b) {
    if(a.l==INT_MIN) return b;
    if(b.l==INT_MIN) return a;
    return {
        max(a.l, a.a+b.l),
        max(b.r, b.a+a.r),
        max({a.n, b.n, a.r+b.l}),
        a.a+b.a
    };
}
 
node identity = {INT_MIN, 0, 0, 0};