[백준 C++] 2042번: 구간 합 구하기

1. 문제

https://www.acmicpc.net/problem/2042

 

2. 알고리즘 분류

• 자료 구조
• 세그먼트 트리

 

3. 소스 코드

#include <iostream>
#define MAX_N 1000006

using namespace std;

typedef long long ll;

int N, M, K;
ll arr[MAX_N];
ll tree[4 * MAX_N];

// Segment Tree 생성 함수
ll init(int node, int start, int end) {

	// leaf node인 경우,
	if (start == end) return tree[node] = arr[start];

	int mid = (start + end) / 2;
	int child_node1 = 2 * node;
	int child_node2 = 2 * node + 1;

	// 부모 노드 = 왼쪽 자식 노드 + 오른쪽 자식 노드
	return tree[node] = init(child_node1, start, mid) + init(child_node2, mid + 1, end);
}

ll query(int node, int start, int end, int left, int right) {

	// 현재 범위(start ~ end)가 찾고자하는 범위(left ~ right) 벗어난 경우
	if (left > end || right < start) return 0;

	// 현재 범위(start ~ end)가 찾고자하는 범위(left ~ right) 내인 경우
	if (left <= start && end <= right) return tree[node];

	int mid = (start + end) / 2;
	int child_node1 = 2 * node;
	int chlid_node2 = 2 * node + 1;

	// 왼쪽 자식 노드와 오른쪽 자식 노드 탐색한 후, 두 자식 노드의 합
	return query(child_node1, start, mid, left, right) + query(chlid_node2, mid + 1, end, left, right);
}

void update(int node, int start, int end, int index, ll value) {
	
	// leaf 노드에 도착한 경우,
	if (start == end) {
		tree[node] = value;
		return;
	}

	int mid = (start + end) / 2;
	int child_node1 = 2 * node;
	int child_node2 = 2 * node + 1;
	if (start <= index && index <= mid)	// 좌측 자식 노드인 경우,
		update(child_node1, start, mid, index, value);
	else  // 우측 자식 노드인 경우,
		update(child_node2, mid + 1, end, index, value);

	tree[node] = tree[child_node1] + tree[child_node2];
}

int main() {
	// io 성능 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 수의 개수, M : 수의 변경, K : 구간의 합
	cin >> N >> M >> K;

	// 배열 입력
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	// Segment Tree 생성
	init(1, 0, N - 1);

	// 수의 변경/구간의 합 구하기
	for (int i = 0; i < M + K; i++) {
		ll a, b, c;
		cin >> a >> b >> c;

		if (a == 1) {	// 배열 값 변경
			arr[b - 1] = c;
			update(1, 0, N - 1, b - 1, c);
		}
		else   // 구간 합 계산
			cout << query(1, 0, N - 1, b - 1, c - 1) << '\n';
	}

	return 0;
}

 

4. 알고리즘

 1) Segment Tree 자료 구조

https://uigwonblog.tistory.com/104

[자료구조] Segment Tree(세그먼트 트리)

1. 정의
 - 배열 간격에 대한 정보를 이진 트리에 저장하는 자료 구조

2. 활용
 - 특정 데이터 배열의 구간 합을 계산할 때 O(logN) 시간 복잡도로 계산 가능