Binary Indexed Tree
Introduction
Binary Indexed Tree using java.
Code
public class BIT {
int[] sums;
int n;
public BIT(int n) {
sums = new int[n];
this.n = n;
}
private int lowBit(int i) {
return i & (-i);
}
public void update(int i, int delta) {
for (; i < n; i += lowBit(i)) {
sums[i] += delta;
}
}
public int query(int i) {
int sum = 0;
for (; i > 0; i -= lowBit(i)) {
sum += sums[i];
}
return sum;
}
}