提出 #73369393

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define int long long
using namespace std;

template <typename T>
struct BIT{
    //Fenwick Tree by Fusion15
    vector<T> arr;
    vector<T> tree;
    int n;

    BIT(){
        n = 0;
    }

    BIT(int _n){
        n = _n;
        tree.resize(n + 1, 0);
        arr.resize(n, 0);
    }

    template<typename U>
    BIT(vector<U> &a){
        n = a.size();
        arr.resize(n, 0);
        tree.resize(n + 1, 0);
        // O(n) build
        for(int i = 0; i < n; i++){
            arr[i] = a[i];
            int id = i + 1;
            tree[id] += arr[i];
            int j = id + (id&-id);
            if(j <= n) tree[j] += tree[id];
        }
    }

    void add(int id, T val){
        arr[id] += val;
        for(int i = id + 1; i <= n; i += i&-i){
            tree[i] += val;
        }
    }

    void update(int id, T val){
        T diff = val - arr[id];
        add(id, diff);
    }

    T query(int id){
        T sum = T(0);
        for(int i = id + 1; i > 0; i -= i&-i){
            sum += tree[i];
        }
        return sum;
    }

    T query(int l, int r){
        if(l > r) return T(0);
        return query(r) - query(l - 1);
    }
};

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef Fusion15
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int n, q;
    cin>>n>>q;

    vector<int> a(n);
    for(int &i : a) cin>>i;
    BIT<int> bit(a);

    while(q--){
        int t;
        cin>>t;
        if(t == 1){
            int l, r;
            cin>>l>>r;
            l--, r--;
            cout<<bit.query(l, r)<<'\n';
        }
        else{
            int x, v;
            cin>>x>>v;
            x--;
            bit.update(x, v);
        }
    }

    return 0;
}

提出情報

ジャッジ結果