[BOJ/C++] 2042(구간 합 구하기)

1. Link

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

2. 풀이 과정

1. 1,000,000개의 배열에 대해 b부터 c까지의 배열의 합을 구하여라 -> 세그먼트 트리
2. ~번째부터 ~번째까지의 합을 -> 세그먼트 트리(구간 합)

• 처음에는 암기식으로 코드를 짰는데, 그 이유로 중요한 코딩 테스트에서 고배를 마신 적이 있어 차분히 분석했던 문제입니다.

위 링크의 1번 예시를 통해 간단하게 알아보도록 하겠습니다.

위 내용대로면, 1~5 까지를 각 노드에 집어넣습니다. 그리고 4개의 쿼리는 각 다음과 같습니다.

1 3 6: 3번째 인덱스의 값을 6으로 바꿉니다.
2 2 5: 배열의 2부터 5까지의 합을 구합니다.
1 5 2: 5번째 인덱스의 값을 2로 바꿉니다.
2 3 5: 배열의 3부터 5까지의 합을 구합니다.

이 쿼리를 해결하는 과정을 한 번 알아보도록 하겠습니다.

우선 1부터 5까지의 값을 대입하는 것으로 위와 같은 세그먼트 트리 구조를 가집니다.

1 3 6: 다음과 같이 3번째 인덱스의 값을 변경한 후, 해당 인덱스의 영향을 받는(합에 영향을 끼치는) 모든 노드의 값을 업데이트합니다.

2 2 5: 2번부터 5번째까지의 배열 값의 합을 구합니다. 전체의 합은 18이지만, 1번 배열의 값인 1을 제외하고 합을 구하면 다음과 같이 17임을 알 수 있습니다.

1 5 2: 5번째 인덱스의 값을 변경한 후, 해당 인덱스의 영향을 받는 모든 노드의 값을 업데이트합니다.

2 3 5: 3번부터 5번째까지의 배열 값의 합을 구합니다. 전체의 합은 15이지만, 1,2번 배열의 합인 3을 제외하고 합을 구하면 다음과 같이 12임을 알 수 있습니다.

3. 정답 코드

#include<iostream>
using namespace std;
#define ll long long

const int MAX = 1000001;
int n, m, k;
ll ar[MAX], seg[MAX << 1];

ll init(int st, int en, int node) {
	if (st == en) return seg[node] = ar[st];
	int mid = (st + en) >> 1;
	return seg[node] = init(st, mid, node << 1) + init(mid + 1, en, (node << 1) + 1);
}

ll update(int st, int en, int node, int idx, ll val) {
	if (idx < st || idx > en) return seg[node];
	if (st == en) return seg[node] = val;
	int mid = (st + en) >> 1;
	return seg[node] = update(st, mid, node << 1, idx, val) + update(mid + 1, en, (node << 1) + 1, idx, val);
}

ll sum(int st, int en, int left, int right, int node) {
	if (left > en || right < st) return 0;
	if (left <= st && en <= right) return seg[node];
	int mid = (st + en) >> 1;
	return sum(st, mid, left, right, node << 1) + sum(mid + 1, en, left, right, (node << 1) + 1);
}

void solution() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> ar[i];
	}
	init(1, n, 1);
	int a, b;
    ll c;
	for (int i = 0; i < m + k; ++i) {
		cin >> a >> b >> c;
		if (a == 1) {
			update(1, n, 1, b, c);
		}
		else {
			cout << sum(1, n, b, c, 1) << '\n';
		}
	}

}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}