Skip to content

Instantly share code, notes, and snippets.

@keon

keon/FenwickTree.cpp

Created Feb 17, 2017
Embed
What would you like to do?
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;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment