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

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

2042번: 구간 합 구하기

 

 

세그먼트 트리 구현...

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n, m, k; //수의 개수, 수의 변경 횟수, 구간의 합 구하는 횟수
ll SegmentTree[4000004];
ll arr[1'000'000 + 10];
ll a, b, c;

ll make_SegmentTree(ll node, ll st, ll ed) {
	if (st == ed) return SegmentTree[node] = arr[st];
	ll mid = (st + ed) / 2;
	return SegmentTree[node] = make_SegmentTree(2 * node, st, mid) + make_SegmentTree(2 * node + 1, mid + 1, ed);
}

ll sum(ll node, ll st, ll ed, ll left, ll right) {
	if (left > ed || right < st) return 0;
	if (left <= st && ed <= right) return SegmentTree[node];
	ll mid = (st + ed) / 2;
	return sum(node * 2, st, mid, left, right) + sum(node * 2 + 1, mid + 1, ed, left, right);
}

void update(ll node, ll st, ll ed, ll idx, ll diff) {
	if (idx<st || idx>ed)return;
	SegmentTree[node] += diff;
	if (st == ed)return;
	ll mid = (st + ed) / 2;

	update(node * 2, st, mid, idx, diff);
	update(node * 2 + 1, mid + 1, ed, idx, diff);
}

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;

	for (ll i = 0; i < n; i++) {
		cin >> arr[i];
	}
	make_SegmentTree(1, 0, n - 1);

	for (ll i = 0; i < m + k; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			ll tmp = c - arr[b - 1];
			arr[b - 1] = c;
			update(1, 0, n - 1, b - 1, tmp);
		}
		else {
			cout << sum(1, 0, n - 1, b - 1, c - 1) << '\n';
		}
	}

}