提出 c7d28001-7a3f-4850-af64-422f10718596

コード

#include<iostream>
#include<vector>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

int main() {
	int n;
	cin >> n;
	int twon = 1;
	while (twon < n) twon *= 2;
	vector<int> seg(2 * twon, 0);
	rep(i, n) cin >> seg[twon + i];
	for (int i = twon - 1; i > 0; i--) seg[i] = seg[2 * i] + seg[2 * i + 1];
	int q;
	cin >> q;
	rep(_, q) {
		int x, l, r;
		cin >> x >> l >> r;
		if (x == 1) {
			seg[twon + l - 1] = r;
			int now = (twon + l - 1) / 2;
			while (now > 0) {
				seg[now] = seg[2 * now] + seg[2 * now + 1];
				now /= 2;
			}
		}
		else {
			int ans = 0;
			l += twon - 1;
			r += twon - 2;
			while (l <= r) {
				if (l % 2 == 1) {
					ans += seg[l];
					l++;
				}
				if (r % 2 == 0) {
					ans += seg[r];
					r--;
				}
				l /= 2;
				r /= 2;
			}
			cout << ans << endl;
		}
	}
	return 0;
}

結果

問題	点数	言語	結果	実行時間	メモリ
SegTree - segment tree	100	C++	AC	17 ms	3812 KiB