segment-tree.cpp

ll n, st[4*N], a[N];

void build( int v, int tl, int tr) {
    if (tl == tr)
        st[v] = a[tl];

    else{
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        st[v] = st[v*2] + st[v*2+1];
    }
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
        st[v] = new_val;

    else{
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);

        st[v] = st[v*2] + st[v*2+1];
    }
}

int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return st[v];
    }
    int tm = (tl + tr) / 2;
    int q1 = sum(v*2, tl, tm, l, min(r, tm));
    int q2 = sum(v*2+1, tm+1, tr, max(l, tm+1), r);
    
    return q1 + q2; 
}