세그먼트 트리 (Bottom-up)

# 세그먼트 트리란?

세그먼트 트리란 구간에 대한 쿼리를 효율적으로 처리하기 위한 자료구조로, 각 노드가 자신의 두 자식 노드가 관리하는 구간을 합한 구간에 대한 정보를 갖는 완전 이진 트리이다.

 

# 구현방법 : Bottom-up과 Top-down

구현하는 방법으로는 Bottom-up과 Top-down 방식이 있는데, 기본적인 세그를 구현할 때는 바텀업을 사용하는 편이다. 탑다운은 쿼리를 처리할 때 위에서 아래(루트에서 리프로)로 내려가면서 처리하는 방법이고, 바텀업은 밑에서 위로(리프에서 루트로) 올라가며 처리하는 방법이다. 탑다운은 재귀로 구현하지만 바텀업은 반복문으로 구현하기 때문에 구현하기도 쉽고 실행속도도 빠르다. 바텀업으로 구현할 때, 구현상의 편의를 위해 포화 이진 트리로 구현한다. lazy propagation 같은걸 하려면 탑다운 방식을 쓰는데, 일단은 바텀업 방식만 설명할거다. 탑다운은 레이지할 때 공부해도 충분하다고 생각한다. 사실 나도 레이지하면서 처음 탑다운 구현했던 것 같다. 처음부터 너무 많은 것을 알려고 하지 말자. 헷갈린다.

 

# 세그먼트 트리로 할 수 있는 것

세그트리를 이용하면 어떤 배열의 값이 자주 바뀔 때, 그 배열에서의 임의의 구간에 대해 구간합, 최대값, 최소값 등을 각 쿼리마다 O(lg N)의 시간복잡도로 구할 수 있다.

 

세그트리에서는 두 종류의 쿼리를 처리할 수 있다.

하나는 배열의 한 원소의 값을 바꾸는 쿼리이다.

다른 하나는 닫힌구간 [l, r]에서의 원하는 값을 구하는 쿼리이다.

예를 들어, 구간합을 구하는 세그트리라면 l <= i <= r을 만족하는 i에 대해 a[i]의 값의 합을 구해주는 것이다.

 

물론 일일이 더해주면 시간이 오래 걸릴 것이다.

저 두 쿼리를 모두 빠르게 처리하기 위해 세그먼트 트리를 사용하는 것이다.

세그먼트 트리의 말단 노드는 자기 자신의 값을 갖고 있다. (구간의 길이가 1이라고 생각할 수 있다.)

나머지 노드들은 자신의 자식 노드의 합을 갖게 된다.

예를 들어, a={3, 1, 6, 8, 2}라면

이렇게 세그먼트 트리가 만들어진다.

구현의 편의를 위해 세그트리의 정보를 sg라는 배열의 저장할거다.

이때, 내부노드 i에 대해서 sg[i] = sg[2 * i] + sg[2 * i + 1]로 정의할 수 있다. (노드 i의 왼쪽 자식이 노드 2*i이고, 오른쪽 자식이 노드 2*i+1이다.)

 

# 업데이트

우선, 어떤 값 하나를 바꾸는 쿼리는 어떻게 처리하는지 알아보자.

이 때는 바꾸려는 위치를 담당하는 말단노드의 값을 바꿔주고, 이 노드의 조상노드들만 값을 다시 계산해주면 된다. 변화의 영향을 받는 노드가 조상노드뿐이기 때문이다. (담당하는 구간을 관찰해보면 자명하다.)

예를 들어, a[1]이 7로 바뀐다고 해보자.

이런식으로 바뀌게 된다.

 

이를 구현하는 방법은

up(p, q)가 호출됐을 때, (p=값을 바꿀 노드, q=얼마로 바꿀지)

sg[p]에 q를 덮어씌우고, 반복문을 이용해 p를 2로 계속 나눠주면서 sg[p]의 값을 다시 계산해주면 된다. (앞서 정의한 식에 따라, sg[p] = sg[2 * p] + sg[2 * p + 1])

어떤 노드에서 자신의 노드 번호를 2로 나눈 몫이 부모 노드의 번호가 되기 때문이다.

 

# 구간합

이제 구간합을 어떻게 구하는지 알아보자.

쿼리로 주어진 구간을 우리가 알고있는 몇개의 구간으로 쪼개어 빠르게 계산해줄 것이다.

예를 들어 [1, 4]의 합을 구하라는 쿼리가 주어졌다고 해보자.

파란색으로 색칠된 부분만 더해주면 우리가 원한 값을 구할 수 있다.

저 색칠되는 영역의 수에 비례해 시간이 걸릴텐데, 과연 몇개나 될까?

쿼리로 주어진 구간이 연속한 하나의 구간이기 때문에 모든 레벨에서 색칠되는 노드는 최대 2개임이 보장된다.

왜냐하면 3개가 되면 반드시 부모노드가 같은 두 노드가 존재하게 되고, 이때는 부모노드만 색칠하면 되기 때문이다.

정말 부모노드가 같은게 있을까? 연속하는 구간이었기 때문에 그럴 수밖에 없다.

 

구현할 때는

get(l, r)이 호출됐을 때, (닫힌 구간 [l, r]의 합을 구하는 함수)

l이 r보다 작은동안 2로 계속 나누어줄 건데,

만약 l이 홀수였으면 그 노드의 값을 더해주고, l에 1을 더한다(오른쪽으로 한 칸 움직이기). (왼쪽부분에서 색칠되는 노드임. 홀수 노드는 누군가의 오른쪽 자식이기 때문) => if (l % 2 == 1) ans += sg[l], l++;

만약 r이 짝수였으면 그 노드의 값을 더해주고, r에서 1을 뺀다(왼쪽으로 한 칸 움직이기). (오른쪽부분에서 색칠되는 노드임. 짝수 노드는 누군가의 왼쪽 자식이기 때문) => if (r % 2 == 0) ans += sg[r], r--;

반복이 끝나고 l과 r이 같다면 이 노드의 값을 더해준다.(색칠되는 노드지만 반복문에서 안 더해줬기 때문. 만약 모든 색칠된 노드가 더해지고 반복문이 종료되면 l과 r이 엇갈려서 l>r이 된다.) => if (l==r) ans += sg[l];

 

여기서 다시 시간복잡도를 생각해볼 수 있는데, 최악의 경우는 l과 r이 1이 되면서 반복이 종료되는 경우이다. 이 때 l과 r이 2로 나눠지면서 1에 도달하기까지 O(lg N)밖에 걸리지 않는다.

 

# 세그먼트 트리 생성하기

처음에 세그먼트 트리를 만들어주기 위해 베이스 값을 구해야 된다.

베이스는 어느 노드부터 말단 노드인지를 알려주는 값이라고 생각하면 된다.

N개가 입력으로 주어진다고 하면 최소 N개의 말단노드가 필요한 것이기 때문에 N보다 크거나 같은 가장 작은 2의 거듭제곱수를 구해주면 된다. 반복문 돌려주면 구할 수 있다.

 

# 연습문제

'구간 합 구하기'는 구간합 세그를 연습할 수 있는 좋은 문제이다.

#include <iostream>
#include <cstdio>
#define N 1000005
using namespace std;

typedef long long ll;
ll n, m, k, Q, ba, sg[N * 4];

// 업데이트
void up(ll p, ll q) {
	p += ba;
	sg[p] = q;
	for (p /= 2; p > 0; p /= 2) sg[p] = sg[p * 2] + sg[p * 2 + 1];
}

// 구간합
ll ge(ll p, ll q) {
	ll re = 0;
	p += ba; q += ba;
	while (p < q) {
		if (p % 2 == 1) re += sg[p], p++;
		if (q % 2 == 0) re += sg[q], q--;
		p /= 2; q /= 2;
	}
	if (p == q) re += sg[p];
	return re;
}

int main() {
	ll i, t1, t2, t3;
	cin >> n >> m >> k;
	Q = m + k;
    
	// 베이스 구하기
	for (ba = 1; ba < n; ba *= 2);
    
	// 입력
	for (i = 0; i < n; i++) scanf("%lld", &sg[ba + i]);
    
	// 처음 세그 만들어주기
	for (i = ba - 1; i > 0; i--) sg[i] = sg[i * 2] + sg[i * 2 + 1];
    
	// 쿼리
	while (Q--) {
		scanf("%lld %lld %lld", &t1, &t2, &t3);
		if (t1 == 1) {
			t2--;  // 인덱스 0번부터로 맞추기
			up(t2, t3);
		} else {
			t2--, t3--;  // 인덱스 0번부터로 맞추기
			printf("%lld\n", ge(t2, t3));
		}
	}
    return 0;
}