struct stree {
    vector<long long> tree;
    unsigned int size;
    stree() {
        size = 0;
    }
    stree(const vector<long long> & init_tree) {
        for(size = 1; size < init_tree.size(); size <<= 1);
        tree.assign((size << 1) | 1, 0);
        for(unsigned int i = 0; i < init_tree.size(); i++) {
            update(i, init_tree[i]);
        }
    }

    void update(unsigned int i, long long value) {
        i += size;
        tree[i] = value;
        for(i >>= 1; i > 0; i >>= 1) {
            tree[i] = tree[i << 1] + tree[(i << 1) | 1];
        }
    }

    long long sum(unsigned int l, unsigned int r) {
        long long res = 0;
        for (l += size, r += size; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) {
                res += tree[l];
                l++;
            }
            if ((r & 1) == 0) {
                res += tree[r];
                r--;
            }
        }
        return res;
    }
};