segtree

struct segtree {

    vector<int> tree;
    int size;

    segtree(int n) {
        size = 1;
        while (size < n) {
            size *= 2;
        }
        tree.resize(2 * size - 1);
    }

    void set(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tree[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m) {
            set(i, v, 2 * x + 1, lx, m);
        } else {
            set(i, v, 2 * x + 2, m, rx);
        }
        tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }

    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }

    int sum(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) {
            return 0;
        }
        if (lx >= l && rx <= r) {
            return tree[x];
        }
        int s1 = sum(l, r, 2 * x + 1, lx, (lx + rx) / 2);
        int s2 = sum(l, r, 2 * x + 2, (lx + rx) / 2, rx);
        return s1 + s2;
    }

    int sum(int l, int r) {
        return sum(l, r, 0, 0, size);
    }
};