Segment Tree

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

const int MAXN = 2e5 + 5;
ll tree[4 * MAXN];
ll IDENTITY = 0;
int n;

ll combine(ll a, ll b) { return a + b; }

void build(ll a[], int idx, int lx, int rx) {
    if (lx == rx) { tree[idx] = a[lx]; return; }
    int mid = (lx + rx) / 2;
    build(a, 2 * idx, lx, mid);
    build(a, 2 * idx + 1, mid + 1, rx);
    tree[idx] = combine(tree[2 * idx], tree[2 * idx + 1]);
}

void build(ll a[]) { build(a, 1, 1, n); }

void update(int pos, ll val, int idx, int lx, int rx) {
    if (lx == rx) { tree[idx] = val; return; }
    int mid = (lx + rx) / 2;
    if (pos <= mid) update(pos, val, 2 * idx, lx, mid);
    else update(pos, val, 2 * idx + 1, mid + 1, rx);
    tree[idx] = combine(tree[2 * idx], tree[2 * idx + 1]);
}

void update(int pos, ll val) { update(pos, val, 1, 1, n); }

ll query(int l, int r, int idx, int lx, int rx) {
    if (lx > r || rx < l) return IDENTITY;
    if (lx >= l && rx <= r) return tree[idx];
    int mid = (lx + rx) / 2;
    return combine(query(l, r, 2 * idx, lx, mid),
                   query(l, r, 2 * idx + 1, mid + 1, rx));
}

ll query(int l, int r) { return query(l, r, 1, 1, n); }