BOJ 2042 구간 합 구하기 (C++, Index Tree)

약간 난이도 있는 (기존의 반복문 조건문 보다는) 문제.
세그먼트 트리 혹은 인덱스 트리 등으로 푸는 문제.
지인의 말로는 인덱스 트리만 알아둬도 괜찮다고 세그먼트 트리로 풀수있는 문제도 다 인덱스 트리로 풀 수 있다고 한다. 반대의 경우는 안되는 경우가 있다고 해서 인덱스 트리로 풀어보았다.

 

#define _CRT_SECURE_NO_WARNINGS
#include    <iostream>
#include	<math.h>
using namespace std;
#define LL long long

int start_idx = 1;
LL *arrN;


int ceil_num(double n) // 그냥 올림 함수 만들었음. 
{
	int c = (int)n;

	if (n < 0 || n == (double)c)
	{
		return c;
	}
	else
	{
		return c + 1;
	}
}

void update_tree(int idx, LL num)
{
	idx = start_idx + idx - 1; // 시작 인덱스에 넣어 줌. -> 1부터 시작할거라 여기서 -1 해주면 편하게 할 수 있을듯. 
	arrN[idx] = num;
	idx = idx / 2; // 해당 노드의 부모 노드는 /2 한게 될것임. 8,9 /2 -> 4 //// 10,11 /2 -> 5 

	while (idx > 0) { //부모 노드부터 시작해서/ 부모 노드의 부모노드까지 쭉 더해줄 수 있음. // 
		arrN[idx] = arrN[idx * 2] + arrN[idx * 2 + 1];  // 4의 자식은 *2 / *2+1 이므로 4*2 = 8/ 4*2+1 = 9 /// 자식노드 둘의 합으로 업데이트 해줌. 
		idx = idx / 2;
	}
}

LL query(int s, int e)  // 합을 구하는 경우 시작과 끝을 잡아주고 구간합을 구할 수 있는 곳은 구간 합으로, 부모가 안되면 리프노드를 통해서 구하면 됨. 
{
	LL tot = 0;

	int start = start_idx + s - 1; // 여기서도 update_tree처럼 - 1 각각 해줘야 함. 리프노드의 시작은 start_idx이므로 기본으로 붙어있음.
	int end = start_idx + e - 1;
	
	// start % 2 == 1이라는 것은 시작 인덱스가 홀수라는 것임. -> 2~7번인덱스까지의 합을 구하는 경우. 
	// 2번 인덱스가 start 일떄 실제 인덱스는 8개 입력 기준으로 start_idx + s - 1 = 8 + 2 - 1 -> 9가 됨. 9번 인덱스의 값은 8번이없으니 부모 노드값을 사용할 수 없고 -> 리프노드를 그대로 더해주어야 함. 
	// end % 2 == 0 도 마찬가지로, end는 실제로 start_idx + e - 1 = 8 + 7 - 1 -> 14가 됨. 14번 인덱스의 값은 14 + 15가 리프노드를 모두 포함한다면 부모노드를 사용할 수 잇지만 15번은 구간 합에 포함되지 않으니 14번 리프노드 값만 더해주게 됨 
	// 두 if에 걸리지 않으면 부모 노드로 넘어가고 넘어가면 됨. 
	//마지막으로 start == end가 된다면 이게 나머지 값들의 루트 노드가 되어 나머지값을 일일이 더할 필요 없이 루트 값을 더해주면 이게 나머지 모두의 합이 됨. 

	//                    1  
	//        2                      3 
	//  4           5          6           7
	//8    9    10    11    12    13    14    15
	// 2~7번 인덱스는 사실상 9~14번 인덱스 이므로 / 9번, 14번 인덱스(리프노드) 합 + 10~13번은 5, 6번 부모노드값에 10+11 -> 5 / 12+13 -> 6 으로 계산되어있으므로 가져다 쓰면 됨.

	while (start <= end) 
	{
		if (start % 2 == 1) 
		{
			tot += arrN[start]; // 9, 5가 지나가고 나면 3으로 끝남 
			start++;
		}
		if (end % 2 == 0)
		{
			tot += arrN[end]; // 14, 6이 되고 나면 2로 끝남 
			end--;
		}
		start /= 2;
		end /= 2;
	}
	
	
	return tot;
}


int main()
{
	int N, M, K;
	
	scanf("%d", &N);
	scanf("%d", &M);
	scanf("%d", &K);
	

	int depth = ceil_num(log2(N) / log2(2)); // index tree의 depth , binary tree 이므로 N을 포함할수 있어야 하고 
	// N이 8일 경우 3개의 depth면 리프노드부터 4-2-1  2^depth로 이뤄지게 됨. 
	//  2^depth >= N 인 최소 depth >> 양쪽에 로그를 취하면 depth >= log₂N

	int len_tree = pow(2, depth + 1) ; // 전체 할당할 크기 
	// 할당할 크기는 등비수열과 같다고 보면 될듯. 8개인 경우 8 + 4 + 2 + 1 = 15(16-1)개가 필요할것으로 보임 
	// 2^n + 2^n-1 .... 2^0 = 2^n+1-1정도로 보면 될듯. 인덱스 편하게 1부터 시작하는것으로 0번 인덱스 버리고 하려면 -1을 안하고 써도 될듯? 함 
	arrN = (LL*)calloc(len_tree, sizeof(LL)); // 구한 길이만큼 할당 
	
	start_idx = pow(2, depth); // 시작 인덱스는 해당 위치부터 시작 
	// 1번 인덱스를 루트노드로 본다면, 1 / 2 3 / 4 5 6 7 / 8~16 순서로 점점 리프노드로 값이 들어가게 될듯. 
	// 우리는 처음 값을 받을 때 리프노드 부터 받아서 이를 기준으로 부모노드를 채워줄 것이므로 
	// 8번부터 받으면 됨. 현재 depth는 8개 기준 3이고, 이때의 리프노드 시작인덱스는 2^depth와 같음 

	for (int i = 1; i <= N; ++i) // i 위치에 넣기 계산 쉽게 하기 위해 1로 시작함. 0번 인덱스는 사용하지않음 
	{
		LL t = 0;
		scanf("%lld", &t);
		update_tree(i, t); // 트리에 값을 넣고, 넣을 때마다 바로 부모노드를 업데이트 하기 위해 함수로 만듬 
	}
	
	for (int i = N + 2; i <= N + M + K + 1; ++i)
	{
		int a, b;
		LL c;
		scanf("%d %d %lld", &a, &b, &c);

		if (a == 1)
		{
			update_tree(b, c); // 동일하게 가져가면 됨. 8번 이후의 리프노드만 변경될것이고 이에 따라 부모노드들을 업데이트 하면 됨 
		}
		else if (a == 2)
		{
			LL tot = query(b, c); 
			printf("%lld\n", tot);
		}
		else
		{
			return -1;
		}
	}
	
	return 0;
}

간만에 코드가 조금 길어졌는데, 주석 쓰느라 길어진것도 있다.
인덱스 트리는 이진트리로 주어진 값들의 배열이 리프노드가 되고, 부모노드가 아래 리프노드 2개씩의 합, MAX, MIN등 이 되어 구간 합, 구간 최대 최소값 구하기에 좋은 구조이다.
-2^63 ~ 2^63-1은 long long 타입이 커버가능해서 사용했다.
주석으로 거의 설명을 해서 추가로 설명할게 크게 없는 듯 하다.