提出 ddc4c189-24a9-4687-b29a-f37c208b1834

コード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> v(n);
    for (int& k : v) cin >> k;
    vector<int> seg(2 * n);
    for (int i = 0; i < n; i++) {
        seg[i + n] = v[i];
    }
    for (int i = n; i--; ) {
        seg[i] = seg[i << 1] + seg[(i << 1) + 1];
    }
    int q; cin >> q;
    for (int _ = 0; _ < q; _++) {
        int type; cin >> type;
        if (type == 1) {
            int p, x; cin >> p >> x;
            p--; p += n;
            seg[p] = x;
            while (p >>= 1) seg[p] = seg[p << 1] + seg[(p << 1) + 1];
        }
        else {
            int l, r; cin >> l >> r; --l; --r;
            l += n, r += n;
            int sum = 0;
            for (; l < r; l >>= 1, r >>= 1) {
                if (l & 1) sum += seg[l++];
                if (r & 1) sum += seg[--r];
            }
            cout << sum << endl;
        }
    }
}

結果

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