백준 2042번 구간 합 구하기 문제 풀이 (C++)

백준 2042번 구간합 구하기

아이디어

구간합을 구하는 문제

arr[i] = arr[i - 1] + num;

과 같이 단순한 식으로 n =1000000이라는 큰 범위를 가지고, 잦은 업데이트가 있는 이 문제를 해결 할 수가 없다.
따라서 구간의 합을 저장해 놓는 세그먼트 트리, 펜윅트리를 사용하여 문제를 풀어야한다.

문제 해결

// 펜윅트리 알고리즘을 이용하여 문제를 해결하였다.
#include<bits/stdc++.h>
using namespace std;
#define MAX 1'000'010
//#define INF 60'000'000'000
//#define MOD 1'000'000'007
typedef long long ll;
ll arr[MAX];	// 원본 배열
ll tmp[MAX];	// 펜윅트리 배열
int n, m, k;
void update(ll idx, ll num) {
	while (idx <= n + 1) {	// 구간에 범위 저장
		tmp[idx] += num;
		idx += (idx & -idx);
	}
}
ll sum(ll idx) {
	ll ans = 0;
	while (idx) {	// 구간에 저장한 값 구하기
		ans += tmp[idx];
		idx -= (idx & -idx);
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		update(i, arr[i]);
	}
	m += k;
	while (m--) {
		ll a, b, c; cin >> a >> b >> c;
		if (a == 1) {
			update(b, c - arr[b]);
			arr[b] = c;
		}
		else
        // b ~ c까지의 합이므로 b도 포함 시켜야한다. -> b - 1
			cout << sum(c) - sum(b - 1) << '\n';
	}
	return 0;
}