class BinaryIndexTree{
    vector<int> tree;
    int n;
public:
    BinaryIndexTree(vector<int> &data){
        n = data.size();
        tree = vector<int>(n, 0);
        for(int i = 0; i < n; i++) update(i, data[i]);
    }

    void update(int x, int delta){
        for(int i = x; i < n; i = i | (i + 1)) tree[i] += delta;
    }

    int sum(int x){
        int res = 0;
        for(int i = x; i >= 0; i = (i & (i + 1)) - 1) res += tree[i];
        return res;
    }
};