세그먼트 트리

오랜만에 돌아온 알고리즘 공부 시간!

 

세그먼트 트리의 필요성

A1, A2, … AN 의 수열이 있을 떄, L, R을 입력 받아서 AL 부터 AR 까지의 수열의 합을 구하라.

→ 이런 쿼리가 있다면, 누적합을 이용해서 sum[R] - sum[L-1]을 통해서 쉽게 구할 수 있을 것이다.

→ 하지만, 이렇게 누적합을 구하는 과정에서 중간에 수열의 값이 변한다면, 각각의 누적합에 대해 연산을 실시해야하므로 O(N) 의 시간복잡도가 걸린다.

 

→ 이러한 연산을 효율적으로 실행할 수 있게 해주는 기법이 세그먼트 트리 기법이다.

 

세그먼트 트리란

• 각 노드는 특정 구간을 대표한다.
• 노드들은 이진트리 구조를 이룬다. (부모 노드가 대표하는 구간은 자식 노드가 대표하는 구간의 합집합이다. )
• 총 길이는 2^k 꼴일 때, 비 재귀 방식에도 유용하고 이해에도 도움이 되기 떄문에 N이상의 2^k 꼴의 수를 사용한다.

세그먼트 트리의 특징

• 임의의 인덱스에 대해 그 인덱스를 포함하는 노드들이 O(logN) 개 존재한다.

• 임의의 구간에 대해 최대 O(logN) 개의 서로 겹치지 않는 구간들의 합으로 표현할 수 있다.

(길이 5짜리 구간이 절반으로 갈라졌을 떄 왼쪽 3, 오른쪽 2로 갈라졌다면 3은 이진수로 11, 2는 10이므로왼쪽 아래 구간에서 가장 아래 1칸과 그위 오른쪽 2칸, 오른쪽 아래 구간에서 왼쪽 2칸을 차지한다고 생각할 수 있다. )

• 세그먼트 트리의 각 노드는 자신이 담당하는 구간에 공통적으로 더해진 수를 저장한다.
  • 점의 값 업데이트: 해당 점을 포함하는 모든 구간에 점의 값을 더하거나 빼서 업데이트한다.
  • 구간의 값 업데이트: 해당 구간을 포함하는, 갈라진 구간들에 대해 값을 더하거나 빼서 업데이트 한다.

세그먼트 트리의 사용

• 점 갱신/ 구간 최대, 최소 값 구하기
• 구간에 값 더하기 / 점의 값 구하기
• 구간에 Ai = max(Ai, X) 연산 취하기 / 한점에 적힌 값 구하기
• 구간에 값 더하기/ 구간의 합 구하기/ 구간의 최댓값 구하기
• etc

세그먼트 트리 구현하기

• 재귀 방식: 구현은 좀 더 시간이 걸리고 실제로도 시간이 더 걸리는 반면, 복잡한 연산을 취하기 좋은 확장성을 갖고 있다.
• 비 재귀 방식 : 복잡하지 않은 간단한 걸 구현할 때 구현이 빠르고 실행도 빠르다.
• 재귀 방식의 update

#v 위치의 노드의 값을 x 로 변경 시, 구간의 합에 대한 노드들도 변경
#update(v ,x, 1, 1, SIZE
def update(v, x, node, s, e):
	if(s == e) :
			tree[node] = x
			return
	mid = (s + e)/ 2
	if(v <= mid):
		 update(v, x, 2 * node, s, mid)
	else:
			update(v, x, 2 * node + 1, mid + 1, e)

• 재귀 방식의 query

# L ~ R 구간 사이의 합을 구하는 쿼리
# (L부터 R까지의 값을 찾고자 한다.) (node, node가 포함하는 범위의 왼쪽, 오른쪽 끝)
# query(L, R, 1, 1, SIZE)
def query (L ,R, node, S, E):
	if(S > R || E < L): # 구하고자 하는 구간을 벗어난 경우
		return 0
	elif(L <= S && E <= R): #구하고자 하는 구간을 S, E가 포함할 때
		return tree[node]
	else:
		mid = (S + E)/2
		return query(L, R, node * 2, S, mid+1, size) + query(L ,R, node * 2 + 1, mid + 1, E, size)

• 비 재귀 방식의 update

//update(v,x) : v위치의 노드를 x로 변경. (그 에 따른 구간합도 변경되게.)
void update(v, x){
		v += size - 1;
		tree[v] = x;
		for(int v/2; v >= 1; v /=2)
				tree[v] = tree[v * 2] + tree[v* 2 + 1];
}

• 비 재귀 방식의 query

int query(L, R){
		L += SIZE -1;
		R += SIZE -1; //내가 구하고자하는 인덱스는 트리에서는 size -1 자리의 노드.
		int ret = 0;
		for(; L <= R; L /=2 , R /= 2){
			if(L % 2 == 1) ret += tree[L++];
			if(R % 2 == 0) ret += tree[R--];
		}
	return ret;
}

 

응용 문제 : 백준 12015 https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

푼 코드 :

 

입력받은 수열의 최댓값을 K라고 할 떄, 1 부터 K를 모두 노드로 보고 푼 세그먼트 트리의 방식이다. 

각 세그먼트 트리는 가리키는 구간 내 최대 길이라고 할 수 있다.

n에 대해 0부터 n-1까지의 구간에서의 LIS 값을 구한다음, + 1 값으로 update 해주는 방식으로 진행한다. 

 

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <stack>
#include <cstring>
#include <sstream>
#define FAST cin.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

#define NONE -1
#define INF 19876543
// #define SIZE (1 << 17)
long long SIZE;
vector<int> tree;
// int nums[1001];
// long long ans[91];
int N,T;
long long max(long long a, long long b){
    return a > b ? a: b;

}

void update(unsigned long v, unsigned long x){//v의 자리를 x로 업데이트
    v += SIZE -1;
    tree[v]= x;
    for(v /= 2; v >= 1; v /= 2)
        tree[v] = max(tree[v * 2] , tree[v * 2 + 1]);
}

long long query(unsigned long L, unsigned long R){
    L += SIZE -1;
    R += SIZE -1; //내가 구하고자하는 인덱스는 트리에서는 size -1 자리의 노드.
    long long ret = 0;
    for(; L <= R; L /=2 , R /= 2){
        if(L % 2 == 1) ret = max(ret, tree[L++]);
        if(R % 2 == 0) ret = max(ret, tree[R--]);
    }
    return ret;
}

bool cmp(pair<int, int> a, pair<int ,int >b){
    return a.first < b.first;

}

int main(){
    FAST
    cin >> N;
    SIZE = ( 1 << ((int)log2(N) + 3));
    tree.assign(SIZE, 0);
    int n;
    long long ans = -INF;

    for(unsigned long i = 0; i < N ; i++){
        cin >> n;
        long long best = query(0, n-1);
        // cout << "n , best : " << n << " " << best << "\n";
        update(n, best + 1);
        if (ans < best + 1)
            ans = best + 1;
    }
    cout << ans;

    
}

 

세그먼트 트리의 공부는 서울대학교 학생분의 알고리즘 강의 영상을 참고했다.

https://www.youtube.com/watch?v=Afr0yvd-8bA