Segment Tree Practice 1

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const int inf = 1e9;
    5const long long INF = 1e17; //❄️
    6vector<ll> seg;
    7void build(const vector<int> &a, int indx, int l, int r) {
    8    if (l == r) {
    9        seg[indx] = a[l];
    10        return;
    11    }
    12    int mid = (l + r) >> 1;
    13    build(a, indx * 2, l, mid);
    14    build(a, indx * 2 + 1, mid + 1, r);
    15    seg[indx] = seg[indx * 2] + seg[indx * 2 + 1];
    16}
    17void update(int pos, int val, int indx, int l, int r) {
    18    if (l == r) {
    19        seg[indx] = val;
    20        return;
    21    }
    22    int mid = (l + r) >> 1;
    23    if (pos <= mid) {
    24        update(pos, val, indx * 2, l, mid);
    25    } else update(pos, val, indx * 2 + 1, mid + 1, r);
    26    seg[indx] = seg[indx * 2] + seg[indx * 2 + 1];
    27}
    28ll qry(int ql, int qr, int indx, int l, int r) {
    29    if (r < ql || qr < l) return 0;
    30    if (ql <= l && r <= qr) return seg[indx];
    31    int mid = (l + r) >> 1;
    32    return qry(ql, qr, indx * 2, l, mid) + qry(ql, qr, indx * 2 + 1, mid + 1, r);  
    33 
    34}
    35int main() {
    36    ios::sync_with_stdio(0); cin.tie(0); 
    37    int n, q; cin >> n >> q;
    38    vector<int> v(n + 1);
    39    for (int i = 1; i <= n; i++) cin >> v[i];
    40    seg.assign(4 * n, 0);
    41    build(v, 1, 1, n);
    42    while (q--) {
    43        char c;
    44        int x, y; cin >> c >> x >> y;
    45        if (c == 'U') update(x, y, 1, 1, n);
    46        else {
    47            cout << qry(x, y, 1, 1, n) << " \n"[q > 0];
    48        }
    49        
    50    }
    51    return 0;
    52}