c++/알고리즘

[c++] 인덱스드 트리에 관하여

hojung 2023. 2. 1.

728x90

1. 인덱스드 트리란?

인덱스드 트리란 어떤 수열이 존재할 때 각 구간의 대표값들로 이루어진 트리를 의미한다.

주로 부분합, 부분 곱, 부분 차 등 구간 별 값을 구해야하는 상황에서 많이 사용된다.
또한 수열의 값이 자주 변경되는 상황에서도 많이 사용된다.

누적 합 배열과 같이 처음부터 순서대로 누적되는 합의 배열을 구하는 방식의 경우 중간에 하나의 값이 변경되면 그 값의 인덱스부터 수열의 끝까지 다시 누적합을 구해야하는 치명적인 단점이 있다. 만약 제일 처음 원소가 변경되었다면 모든 누적합 배열을 처음부터 다시 계산해야한다.O(N)이 걸린다.

기본적으로 트리라는 자료구조는 O(logN)의 시간복잡도를 위한 자료구조이다. 시간복잡도를 얻는 대신 공간복잡도를 살짝 trade-off하긴 하지만 요즘 메모리는 여유가 아주 많은 편이라 시간을 줄이는 것이 대부분 더 중점이다.

다음과 같은 트리가 인덱스드 트리에 해당한다. 보면 원본 배열을 두 개씩 잘라 대표값을 위로 올리고 그 대표값들을 다시 두 개씩 잘라 또 다른 대표값을 올린다. 따라서 구간 별 대표값을 O(logN)의 시간복잡도 안에 탐색할 수 있다는 장점이 있다.

2. 구현 부분

위의 그림에서도 알 수 있듯이 인덱스드 트리는 원본 배열보다 많은 공간을 필요로 한다.

위의 그림에서 원본 배열의 크기는 6에 해당한다. 하지만 tree의 depth가 위로 늘어나면서 부족한 오른쪽의 공간이 생겨날 수도 있으므로 우선 해줘야하는 과정은 다음과 같다.

한번

4 5 7 8 11 3 의 구간 합 인덱스드 트리를 구해보겠다.

트리 사이즈 구하기

원본 배열의 크기보다 큰 가장 작은 2의 제곱수를 구한다. 위의 경우 6보다 크며 가장 작은 2의 제곱수는 8이 되겠다. (이 수는 중요하다!)
위에서 구한 제곱수의 * 2를 해주어야한다. (tree가 위로 늘어나기 때문에)(사실 *2 -1이 정확한 수이나 여유를 주기 위해)

위와 같이 구하면 트리가 필요로하는 메모리 크기를 알 수 있게 된다. 메모리 크기를 구했으면 이제 트리를 채워줘야한다.

트리 init

1. 아까 위에서 구해준 원본 배열의 크기보다 크며 가장 작은 2의 제곱수부터 원본 배열을 채워나가준다.

2. 아까 구한 수 8보다 1작은 7부터 내려오며 [index * 2] , [index * 2+ 1] 에 대한 값을 저장하며 내려온다.

위와 같이 저장하면 각 구간 별 대표값이 저장된 인덱스드 트리가 배열 안에 만들어졌다.

다음과 같은 트리가 만들어지게 된다.

트리 init 코드 구현

#include <iostream>
#include <algorithm>
#define MAX 1000000
#define SIZE_MAX 2097152
using namespace std;
int N; // 입력의 크기
int origin[MAX];
int Tree[SIZE_MAX];
int OFFSET = 1;
void init() {
	while(OFFSET < N) OFFSET *= 2;
    for(int i=0; i < N; i++) Tree[OFFSET+i] = origin[i];
    for(int i=N; i < OFFSET; i++) Tree[OFFSET+i] = 0;
    for(int i=OFFSET-1; i > 0; i--) Tree[i] = Tree[i * 2] + Tree[i * 2+1];
}

위와 같이 Tree의 초기 값을 초기화해줄 수 있다.

트리 query

만약 원래 배열의 3번부터 6번까지의 누적합을 인덱스 트리를 통해 알고 싶다면 어떻게 해야할까?

우선 직관적으로 그림을 봤을 때 15와 14를 더하면 4개 수의 누적합을 구할 수 있을 것이라는 생각이 들었다.

그러면 7을 더하면 안되고 3을 더하면 안되고 두 화살표를 위 칸으로 움직여서 (시작 화살표는 오른쪽으로 한칸 끝 화살표는 왼쪽으로 한 칸 움직여야한다. )15와 14를 더해야한다. 그 후 위층으로 올라갈 노드가 없으니 트리 탐색을 종료한다.

이 때 처음 시작한 인덱스는 3 끝 인덱스는 6이다.

위의 그림을 통해 작게 보면 3번째 에서 6번째를 더할 때 7은 더하지 않은 채 올라가고 4번째에서 6번째를 더할 때는

8을 더한 후 누적합을 구해줘야 하는 것을 알 수 있다. 따라서 시작 화살표에서는 인덱스가 짝수일 때는 더하지 않고 홀수가 될 때 더해주는(작업을 수행해주는)것을 확인할 수 있었다. 또한 한 층에서 시작 인덱스가 홀수였다면 (홀수+1 / 2)가 다음 트리의 노드 인덱스가 되는 것을 확인할 수 있었다.

반대로 끝의 화살표의 경우 3에 해당하는 노드까지 누적합을 구할 때는 3을 더하지 않고 위로 올라가야하고 11까지 구해야하는 누적합을 구할 때는 11을 더한 후 트리의 다음 노드 ((11노드 인덱스 -1 )/2)로 이동해야 하는 것을 알 수 있었다.

여기서는 끝의 화살표의 인덱스가 홀수일 때는 더하지 않고 짝수일 때는 더한 후 다음 트리 노드로 이동해야하는 것을 알 수 있었다. 또한 반복문은 시작화살표 < 끝화살표 일 때까지 지속되어야한다.

따라서 코드로 구현하면 다음과 같다.

트리 query 코드 구현

#include <iostream>
#include <algorithm>
#define MAX 1000000
#define SIZE_MAX 2097152
using namespace std;
int N; // 입력의 크기
int origin[MAX];
int Tree[SIZE_MAX];
int OFFSET = 1;
void init() {
	while(OFFSET < N) OFFSET *= 2;
    for(int i=0; i < N; i++) Tree[OFFSET+i] = origin[i];
    for(int i=N; i < OFFSET; i++) Tree[OFFSET+i] = 0;
    for(int i=OFFSET-1; i > 0; i--) Tree[i] = Tree[i * 2] + Tree[i * 2+1];
}

int query(int from, int to) {
	int res=0;
    from += OFFSET; to += OFFSET;
    
    while(from <= to){
    	if(from % 2) res += Tree[from++];
        if((to % 2) == 0) res+=Tree[to--];
        
        from /= 2; to /= 2;
    }
    
    return res;
}

트리 update

만약 트리의 한 노드가 업데이트 되면 어떻게 될까?

해당 노드의 값이 변경된다고 하자 그러면 어떻게 될 것인가

다음과 같은 값들이 변경될 것이다. 이전 누적합 배열의 경우 7부터 모든 노드들을 업데이트해야 했지만 인덱스드 트리에서는 단 4개의 노드만을 변경하면 된다.

7->9로 변경해보겠다.

다음과 같이 업데이트 된다.

위와 같은 하나의 삼각형 모양에서 부모 노드를 i라하면 두 자식 노드의 인덱스는 [i*2] [i*2+1]이 된다.

따라서 업데이트를 idx에 OFFSET을 더해준 후 2씩 나눠가면서 해당 idx의 노드들의 값을 업데이트해주면 된다.

#include <iostream>
#include <algorithm>
#define MAX 1000000
#define SIZE_MAX 2097152
using namespace std;
int N; // 입력의 크기
int origin[MAX];
int Tree[SIZE_MAX];
int OFFSET = 1;
void init() {
	while(OFFSET < N) OFFSET *= 2;
    for(int i=0; i < N; i++) Tree[OFFSET+i] = origin[i];
    for(int i=N; i < OFFSET; i++) Tree[OFFSET+i] = 0;
    for(int i=OFFSET-1; i > 0; i--) Tree[i] = Tree[i * 2] + Tree[i * 2+1];
}

int query(int from, int to) {
	int res=0;
    from += OFFSET; to += OFFSET;
    
    while(from <= to){
    	if(from % 2) res += Tree[from++];
        if((to % 2) == 0) res+=Tree[to--];
        
        from /= 2; to /= 2;
    }
    
    return res;
}

void update(int idx, int val) {
	idx += OFFSET;
    Tree[idx] = val;
    while(idx >= 1) {
    	idx /= 2;
        Tree[idx] = Tree[idx * 2] + Tree[idx * 2 + 1];
    }
}

다음과 같이 코드를 작성할 수 있다.

4. 응용 문제

백준에는 인덱스드 트리를 이용해서 풀 수 있는 많은 문제들이 존재한다. 그 중 2개를 볼 것이다.

1. 구간 합 구하기

2. 입 출력

3. 코드 및 문제해설

위의 설명한 내용을 그대로 적용하면 되는 문제이다. 인덱스드 트리를 구축한다음 1이 들어오면 update함수를 수행해주고

2가들어온다면 query함수를 수행해주면된다.

#include <iostream>
#include <algorithm>

using namespace std;
//전체 가능한 수가 1000000이므로 1000000보다 처음으로 커지는 2의 배수가 offset이 된다. 
//그 후 이 offset의 2배가 되는 수가 배열의 크기가 된다.
#define MAX_N   1000000
#define SZ_TR   2097152

typedef long long ll;

int N,M,K;
int OFFSET = 1;
ll nos[MAX_N]; // 본 배열
ll tree[SZ_TR]; // 본 배열을 토대로 구성한 세그먼트 트리

void init() {
    while(OFFSET<N) OFFSET*=2;//N보다 커지는 최소의 2의 배수
    for(int i=0; i<N; i++) tree[OFFSET+i] = nos[i];// startIndex의 크기는 offset과 같다.
    for(int i=N; i<OFFSET; i++) tree[OFFSET+i] = 0;
	//배열의 앞쪽 부분에 누적합을 채워준다. 
    for(int i=OFFSET-1; i>0; i--) tree[i] = tree[i*2] + tree[i*2+1];
}
ll query(int from, int to) {
    ll res = 0;
    from += OFFSET;     to += OFFSET;
    while(from <= to) {
		//from이 홀수라면 자기 자신을 더한 뒤 from을 ++해준다. 
        if(from % 2 == 1)    res += tree[from++];
        //to 가 짝수라면 자기 자신을 더해준 후 --해준다.
				if(to % 2 == 0)     res += tree[to--];

        from /= 2;  to /= 2;    
    }
    return res;
}
void update(int idx, ll val) {
    idx += OFFSET;
    tree[idx] = val;
    while(idx > 0) {
        idx /= 2;
        tree[idx] = tree[idx*2] + tree[idx*2+1];
    }
}
int main() {

    int com;
    ll x,y;
    scanf("%d %d %d",&N,&M,&K);
    for(int i=0; i<N; i++) scanf("%lld",nos + i);
    init();
    for(int i=0; i<M+K; i++) {
        scanf("%d %lld %lld",&com,&x,&y);
        if(com == 1) update(x-1,y);
        if(com == 2) printf("%lld\n",query(x-1,y-1));
    }

2. 구간 곱 구하기

2. 입출력

3. 코드 및 해설

위의 문제와 동일하나 구간의 대표값을 찾는 로직만 조금 변경해주면 되는 문제이다. 위의 구간 합을 구하는 문제는 구간 별로 대표값을 두 개의 합으로 설정했으나 이 문제에서는 두 노드의 곱을 구한 후 1000000007로 나눠주면 된다.

//11505 구간곱 구하기
/*
	인덱스드 트리 + 유클리드 호제법
	인덱스드 프리는 완전이진트리이다. 
*/
#pragma warning (disable : 4996)
#include <cstdio>

const int SIZE = 2097152; // 2^21
const int BASE = 1048576; // 2^20
const int MOD = 1000000007;
long long ITree[SIZE];

int N, M, K; // N배열 사이즈 M : 변경횟수, K:구간곱연산횟수
void update( int b, int c) {
	b += BASE;//위치
	ITree[b] = c;
	while ((b/=2) > 0) {
		ITree[b] = ITree[b * 2] * ITree[b * 2 + 1] % MOD;
	}
};

int calc(int b, int c) {
	b += BASE, c += BASE;
	long long tmp = 1;
	while (b <= c) {
		if (b & 1) { // b가 오른쪽 자식이면
			tmp = tmp* ITree[b++] %MOD;
		}
		b /= 2;
		if (c % 2 == 0) { // c가 왼쪽 자식이면
			tmp = tmp * ITree[c--] % MOD;
		}
		c /= 2;
	}
	return (int)tmp;
}
int main() {
	scanf("%d %d %d", &N, &M, &K);

	//구간 곱을 구할 때에는 항등원이 1이다. 
	for (int i = BASE + 1; i <= BASE + N; i++) {
		scanf("%d", &ITree[i]);
	}
	for (int i = BASE + N + 1; i < SIZE; i++) {
		ITree[i] = 1; // 곱셈에 대한 항등원은 1이므로 1로 초기화를 해준다. 
	}
	for (int i = BASE - 1; i > 0; i--) {
		ITree[i] = ITree[i * 2] * ITree[i * 2 + 1] % MOD;
	}//인덱스드 트리 Init

	int S = M + K;

	for (int i = 0; i < S; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1) { // b번지에 있는 값을 c로 변경
			update(b, c);
		}
		else { // b번지부터 c번지까지의 구간 곱 출력
			printf("%d\n", (int)calc(b, c));
		}
	}

	return 0;
}

ㅓㅓ

ㅓㅓㅓㅓ

ㄷㅓㅗㅏㅓㅓㅏㅗ9

ㅓㅗㅗㅗㅗㅓ