pers segtree

struct node {
    int l, r;
    int value;

    node() : l(-1), r(-1), value(0) {}

    node(int l, int r, int x) : l(l), r(r), value(x) {}
};

const int N = 3000000;
node tree[N];
int last;

int build(int lx, int rx, const vector<int> &input) {
    node a;
    if (lx == rx - 1) {
        a.value = input[lx];
        tree[last] = a;
        return last++;
    }
    int m = (lx + rx) / 2;
    a.l = build(lx, m, input);
    a.r = build(m, rx, input);
    a.value = tree[a.l].value + tree[a.r].value;
    tree[last] = a;
    return last++;
}

int update(int i, int v, int x, int lx, int rx) {
    node a;
    if (lx == rx - 1) {
        a.value = tree[x].value + v;
        tree[last] = a;
        return last++;
    }
    int m = (lx + rx) / 2;
    if (i < m) {
        a.l = update(i, v, tree[x].l, lx, m);
        a.r = tree[x].r;
    } else {
        a.l = tree[x].l;
        a.r = update(i, v, tree[x].r, m, rx);
    }
    a.value = tree[a.l].value + tree[a.r].value;
    tree[last] = a;
    return last++;
}

int sum(int l, int r, int x, int lx, int rx) {
    if (r <= lx || rx <= l) {
        return 0;
    }
    if (l <= lx && rx <= r) {
        return tree[x].value;
    }
    int m = (lx + rx) / 2;
    int left = sum(l, r, tree[x].l, lx, m);
    int right = sum(l, r, tree[x].r, m, rx);
    return left + right;
}