[BOJ] 2042 : 구간 합 구하기

#include <iostream>
using namespace std;
typedef long long ll;
const int n_ = 1048576 + 1;

int n, m, k, arr[n_];
ll tree[n_ * 2];

ll init(int now, int lft, int rgt) {
	if (lft == rgt) return tree[now] = arr[lft];
	return tree[now] = init(now * 2, lft, (lft + rgt) / 2) + init(now * 2 + 1, (lft + rgt) / 2 + 1, rgt);
}

void upd(int now, int idx, int lft, int rgt, ll dif) {
	if (idx < lft || rgt < idx) return;
	tree[now] += dif;
	if (lft != rgt) {
		upd(now * 2, idx, lft, (lft + rgt) / 2, dif);
		upd(now * 2 + 1, idx, (lft + rgt) / 2 + 1, rgt, dif);
	}
}

ll qry(int now, int bgn, int end, int lft, int rgt) {
	if (rgt < bgn || end < lft) return 0;
	if (bgn <= lft && rgt <= end) return tree[now];
	return qry(now * 2, bgn, end, lft, (lft + rgt) / 2) + qry(now * 2 + 1, bgn, end, (lft + rgt) / 2 + 1, rgt);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	init(1, 1, n);

	for (int i = 0; i < m + k; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		if (a == 1) upd(1, b, 1, n, c - arr[b]), arr[b] = c;
		else cout << qry(1, b, c, 1, n) << "\n";
	}

	return 0;
}

#include <stdio.h>
typedef long long ll;
const int n_ = 1e6 + 1;

int n, m, k;
ll num[n_], bit[n_];

inline void upd(int h, ll v) {
	for (int i = h; i <= n; i += i&-i) bit[i] += v;
}

ll qry(int h) {
	ll ret = 0;
	for (int i = h; i; i -= i&-i) ret += bit[i];
	return ret;
}

int main() {
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 1; i <= n; i++)
		scanf("%lld", &num[i]), upd(i, num[i]);

	for (int i = 0; i < m + k; i++) {
		ll a, b, c;
		scanf("%lld %lld %lld", &a, &b, &c);
		if (a == 1) upd(b, c - num[b]), num[b] = c;
		else printf("%lld\n", qry(c) - qry(b - 1));
	}

	return 0;
}