Introduction to Binary Index Tree or Fenwick Tree
Binary Index Tree (BIT) aka Fenwick Tree is a simple data structure that has O(LogN) complexity in updating element in a list and querying the accumulate sum or sum between a given range.
You can achieve O(1) constant complexity in calculating the accumulate sum or interval sum using a prefix sum array with O(N) space. Or you can store the original numbers and enjoy the O(1) update.
The Binary Index Search is simpler to implement than a Segment Tree (which we will cover in a separate post C++ Implementation of Segment Tree). You can pass an array/vector into the BIT constructor or, alternative you can specify the maximum number of elements in the BIT data structure. Usually, we pad a zero in the begining so that when we compute the range sum between two indices, we don’t need to worry about index being out of range e.g. -1.
C++ Binary Index Tree Implementation (Fenwick Tree)
The Binary Index Tree implementation in C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | class BIT { private: vector<int> data; public: BIT(vector<int> nums) { data.resize(nums.size() + 1); for (int i = 0; i < nums.size(); ++ i) { add(i, nums[i]); } } BIT(int n) { data.resize(n + 1); } // add the value val to index i void add(int i, int val) { ++ i; while (i < data.size()) { data[i] += val; i += (i & (-i)); } } // get the prefix sum from 0 to i int sum(int i) { ++ i; int v = 0; while (i) { v += data[i]; i -= (i & (-i)); } return v; } // get the range sum between [i, j] int queryRange(int i, int j) { return sum(j) - sum(i - 1); } }; |
class BIT {
private:
vector<int> data;
public:
BIT(vector<int> nums) {
data.resize(nums.size() + 1);
for (int i = 0; i < nums.size(); ++ i) {
add(i, nums[i]);
}
}
BIT(int n) {
data.resize(n + 1);
}
// add the value val to index i
void add(int i, int val) {
++ i;
while (i < data.size()) {
data[i] += val;
i += (i & (-i));
}
}
// get the prefix sum from 0 to i
int sum(int i) {
++ i;
int v = 0;
while (i) {
v += data[i];
i -= (i & (-i));
}
return v;
}
// get the range sum between [i, j]
int queryRange(int i, int j) {
return sum(j) - sum(i - 1);
}
};Here is another implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class BIT { private: vector<int> tree; int n; public: BIT(int _n) : n(_n), tree(_n + 1) {} static constexpr int lowbit(int x) { return x & (-x); } void update(int x, int d) { while (x <= n) { tree[x] += d; x += lowbit(x); } } int query(int x) const { int ans = 0; while (x) { ans += tree[x]; x -= lowbit(x); } return ans; } }; |
class BIT {
private:
vector<int> tree;
int n;
public:
BIT(int _n) : n(_n), tree(_n + 1) {}
static constexpr int lowbit(int x) {
return x & (-x);
}
void update(int x, int d) {
while (x <= n) {
tree[x] += d;
x += lowbit(x);
}
}
int query(int x) const {
int ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
};Java Binary Index Tree Implementation (Fenwick Tree)
The Java Implementation of Fenwick Tree is quite similar to C++ version.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | class BinaryIndexTree { int[] counts; int size; public BinaryIndexTree(int n) { size = n + 1; counts = new int[size]; } public BinaryIndexTree(int[] counts) { size = counts.length() + 1; this.counts = counts; for (int i = 0; i < counts.length(); ++ i) { add(i, counts[i]); } } // add val to nums[i] and update the tree. public void add(int i, int val) { ++i; while (i < size) { counts[i] += val; i += Integer.lowestOneBit(i); } } // get the prefix/accumulate sum from [0, i] public int sum(int i) { ++i; int ans = 0; while (i &t; 0) { ans += counts[i]; i -= Integer.lowestOneBit(i); } return ans; } // get the range sum between [i, j] public int queryRange(int i, int j) { return sum(j) - sum(i - 1); } } |
class BinaryIndexTree {
int[] counts;
int size;
public BinaryIndexTree(int n) {
size = n + 1;
counts = new int[size];
}
public BinaryIndexTree(int[] counts) {
size = counts.length() + 1;
this.counts = counts;
for (int i = 0; i < counts.length(); ++ i) {
add(i, counts[i]);
}
}
// add val to nums[i] and update the tree.
public void add(int i, int val) {
++i;
while (i < size) {
counts[i] += val;
i += Integer.lowestOneBit(i);
}
}
// get the prefix/accumulate sum from [0, i]
public int sum(int i) {
++i;
int ans = 0;
while (i &t; 0) {
ans += counts[i];
i -= Integer.lowestOneBit(i);
}
return ans;
}
// get the range sum between [i, j]
public int queryRange(int i, int j) {
return sum(j) - sum(i - 1);
}
}The Fenwick Tree allows you to mutate the list and compute the range sum in both O(logN) – which is a good balance if you need to update and query many many times.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: The Simple Console Rocket Animation in Python
Next Post: Algorithms to Compute the Fibonacci String Sequence
