[백준] 구간 합 구하기

세그먼트 트리의 가장 기본이 될수 있는 문제를 풀어 보았다.
세그먼트 트리의 시간복잡도는 logN 이지만 초기화시 시간 복잡도는 N이 걸리는 자료구조이다.
그렇기 때문에 배열의 특정 구간의 연산값을 반복해서 조회할 경우 유용한 알고리즘이다.
세그먼트 트리의 원리는 상당히 간단하다.

연산을 수행해야 하는 배열의 길이를 기준으로 1/2씩 구간을 쪼개어 내려간 뒤 길이가 1일 되었을때 배열의 값을 세그먼트 트리용 배열에 넣어준 다음 그 값을 반환하면 된다.
재귀로 호출되기 때문에 반환된 값에 대해서 합을 구한 뒤 트리용 배열에 저장하고 해당 값을 반환해 나가면 최초 시작한 시점으로 돌아가게 되면 전체 범위에 대한 값을 얻을 수 있다.

#include <iostream>

using namespace std;

using ll = long long;

ll dp[1 << 21];
ll buf[1'000'001];

//입력된 값을 이용하여 세그먼트 트리 배열 정보를 초기화(N)
ll init(int left, int right, int depth) {
	if (left == right) return dp[depth] = buf[left];

	int mid = (left + right) / 2;

	return dp[depth] = search(left, mid, depth * 2) + search(mid + 1, right, depth * 2 + 1);
}

// 갱신되는 배열을 위치를 찾아 도착 지점에서 부터 정보를 갱신 (logN)
ll update(int left, int right, int target, ll num, int depth) {
	if (left > target || right < target) return dp[depth]; // 갱신 범위를 넘어간 구간의 값은 수정하지 않는다
	if (left == right && left == target) return dp[depth] = num; // 최종 목적지에 도착하여 갱신을 시작


	int mid = (left + right) / 2;

	return dp[depth] = update(left, mid, target, num, depth * 2) + update(mid + 1, right, target, num, depth * 2 + 1);
}

// 요구되는 구간의 합을 탐색(logN)
ll sol(int left, int right, int target_l, int target_r, int depth) {
	if (right<target_l || left>target_r) return 0; // 구간을 벗어난 탐색에서는 0을 반환 
	if (right <= target_r && left >= target_l) return dp[depth]; // 범위안 구간시 바로 반환

	int mid = (left + right) / 2;

	return sol(left, mid, target_l, target_r, depth * 2) + sol(mid + 1, right, target_l, target_r, depth * 2 + 1);
}


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int N, M, K;
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		cin >> buf[i];
	}
	init(1, N, 1);

	ll a, b, c;
	for (int i = 0; i < M + K; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			update(1, N, b, c, 1);
		}
		else {
			cout << sol(1, N, b, c, 1) << "\n";
		}
	}
}