Submission #73369028

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegmentTree {
    int n;
    vector<long long> tree;

    // コンストラクタ
    SegmentTree(int size) {
        n = 1;
        while (n < size) n *= 2;
        tree.assign(2 * n - 1, 0);
    }

    // 値をセット（初期構築用）
    void set(int i, long long x) {
        tree.at(i + n - 1) = x;
    }

    // 構築
    void build() {
        for (int i = n - 2; i >= 0; i--) {
            tree.at(i) = tree.at(2 * i + 1) + tree.at(2 * i + 2);
        }
    }

    // 点更新（a[i] = x）
    void update(int i, long long x) {
        int k = i + n - 1;
        tree.at(k) = x;

        while (k > 0) {
            k = (k - 1) / 2;
            tree.at(k) = tree.at(2 * k + 1) + tree.at(2 * k + 2);
        }
    }

    // 区間 [a, b)
    long long query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return tree.at(k);

        long long vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        long long vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }

    // 外部用
    long long query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

int main(void){
    ll N, Q;
    cin >> N >> Q;
    SegmentTree S(N);
    for(int i = 0; i < N; i++) {
        int s;
        cin >> s;
        S.set(i, s);
    }
    S.build();
    
    for(int i = 0; i < Q; i++) {
        int q;
        cin >> q;
        if(q == 1) {
            int L, R;
            cin >> L >> R;
            cout << S.query(L - 1, R) << endl;
        }else {
            int X, V;
            cin >> X >> V;
            S.update(X - 1, V);
        }
    }
    
    return 0;
}

Submission Info

Judge Result