Fenwick Tree
A fenwick tree or binary indexed tree is a kind of data structure used to maintain the preffix sums of an ordered list of numbers.
The main concept of fenwick tree is function, which is the number of which all bits are assgined to zero without the last in the given number's binary representation. Each node in fenwick tree holds the sum of
In most programming languages, can be implemented like this:
int lowbit(int x) {
return x & (-x);
}Implementation
class bit {
public:
int *sum, size;
bit(int size) {
this->size = size;
this->sum = new int[size + 1];
for (int i = 0; i <= size; i++) {
this->sum[i] = 0;
}
}
void add(int pos, int value) {
while (pos <= this->size) {
sum[pos] += value;
pos += (pos & (-pos));
}
}
int query(int pos) {
int result = 0;
while (pos > 0) {
result += sum[pos];
pos -= (pos & (-pos));
}
return result;
}
};