Building Fenwick Tree
Building a Fenwick tree from an array can be done in O(n) by initializing the BIT with zeros and then performing n point updates (O(n log n)), or by using a linear construction algorithm. Here we'll show both.
Method 1: Using point updates (O(n log n))
Initialize BIT array with zeros, then for each i from 1 to n, call update(i, arr[i-1]).
Method 2: Linear construction (O(n))
We can fill BIT directly by copying the array and then updating each parent.
public void build(int[] arr) {
n = arr.length;
tree = new int[n + 1];
for (int i = 1; i <= n; i++) {
tree[i] += arr[i-1];
int j = i + (i & -i);
if (j <= n) tree[j] += tree[i];
}
}
Now we can perform point updates and prefix sum queries.
Two Minute Drill
- Fenwick tree can be built in O(n) using linear construction.
- Internal tree array is 1-indexed.
- Each node's parent is i + (i & -i).
- Building time O(n).
Need more clarification?
Drop us an email at career@quipoinfotech.com