Dynamic Range Sum Queries

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 2e18; //❄️
    7struct BIT {
    8    int n;
    9    vector<ll> bit;
    10    BIT(int n) {
    11        this->n = n;
    12        bit.assign(n + 1, 0);
    13    }
    14    void add(int pos, ll val) {
    15        for (int i = pos; i <= n; i += i & -i) {
    16            bit[i] += val;
    17        }
    18    }
    19    ll sum(int pos) {
    20       ll res = 0;
    21        for (int i = pos; i > 0; i -= i & -i) {
    22            res += bit[i];
    23        }
    24        return res;
    25    }
    26    ll sum(int l, int r) {
    27        if (l > r) return 0;
    28        return sum(r) - sum(l - 1);
    29    }
    30 };
    31int main() {
    32    ios::sync_with_stdio(0); cin.tie(0); 
    33    int n, q; cin >> n >> q;
    34    BIT bit(n);
    35    vector<ll> v(n + 1);
    36    for (int i = 1; i <= n; i++) {
    37        cin >> v[i];
    38        bit.add(i, v[i]);
    39    }
    40    while (q--) {
    41        int qry;
    42        cin >> qry;
    43        if (qry == 1) {
    44            int pos; ll val; cin >> pos >> val;
    45            ll diff = val - v[pos];
    46            v[pos] = val;
    47            bit.add(pos, diff);
    48        } else {
    49            int l, r; cin >> l >> r;
    50            cout << bit.sum(l, r) << '\n';
    51        }
    52    }
    53    return 0;
    54}