struct seg_tree {
    vector<int> a;
    vector<int> sum;

    seg_tree(vector<int> b) {
        int n = b.size();
        a = b;
        sum.resize(4 * n);
        build(0, 0, n);
    }

    void build(int id, int l, int r) {
        if (l + 1 == r) {
            sum[id] = l;
            return;
        }
        int m = (l + r) / 2;
        build(id * 2 + 1, l, m);
        build(id * 2 + 2, m, r);
        sum[id] = sum[id * 2 + 1] + sum[id * 2 + 2];
    }

    int get(int id, int l, int r, int lq, int rq) {
        if (l >= rq || lq >= r) {
            return 0;
        }
        if (lq <= l && r <= rq) {
            return sum[id];
        }
        int m = (l + r) / 2;
        int s1 = get(id * 2 + 1, l, m, lq, rq);
        int s2 = get(id * 2 + 2, m, r, lq, rq);
        return s1 + s2;
    }

    void upd(int id, int l, int r, int i, int x) {
        if (l + 1 == r) {
            sum[id] += x;
            return;
        }
        int m = (l + r) / 2;
        if (i < m) {
            upd(id * 2 + 1, l, m, i, x);
        } else {
            upd(id * 2 + 2, m, r, i, x);
        }
        sum[id] = sum[id * 2 + 1] + sum[id * 2 + 2];
    }
};