FenwickTree.cpp

class Fenwick{
private:
    const int maxN = 10000;
public:
    int table[maxN];

    int sumQuery(int a, int b){
        return sumQuery(b) - sumQuery(a-1);
    }

    int sumQuery(int k){
        int ret = 0;
        while (k > 0) {
            ret += table[k];
            k &= k - 1;
        }
        return ret;
    }

    void adjust(int i, int adj){
        while(i < maxN){
            table[i] += adj;
            i += (i & (-i));
        }
    }

    int getValue(int i) {
        return sumQuery(i, i);
    }

    int findFirst(int k) {
        int L = 1, R = maxN - 1;
        while (R - L > 1) {
            int M = (R+L) / 2;
            int val = sumQuery(M);
            if (val < k)
                L = M + 1;
            else
                R = M;
        }
        int LVal = sumQuery(L);
        if (LVal >= k)
            return L;
        return R == L || sumQuery(R) < k ? -1 : R;
    }
};