A Fenwick tree or Binary Indexed Tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Peter Fenwick in 1994 to improve the efficiency of arithmetic coding compression algorithms.
There are situation where we need to execute both update and query operations on an array (typically a number array). Naive solutions may take O(n) time to do a prefix sum search. And when the length of the array get increased this solution will give low performance. BIT can do the operations like prefix sum, point query, update in O(logn) time.
The BIT normally used to perform Segment Query and Point Updates. The below code is a Java implementation of that approach.
public class FenwickTree {
long[] fenwickTree;
int treeSize;
/**
* create a FenwickTree instance with a tree of a given size
*
* @param size
* : size of the original array to consider
*/
public FenwickTree(int size) {
this.treeSize = size + 1;
this.fenwickTree = new long[treeSize];
}
/**
* create a FenwickTree instance with a given array
*
* @param array
*/
public FenwickTree(long[] array) {
this.treeSize = array.length + 1;
this.fenwickTree = new long[treeSize];
for (int i = 1; i < treeSize; i++) {
update(i, array[i - 1]);
}
}
/**
* if a previous value is updated by a new one (eg : 3 by 7), then only the
* changed difference (7-3) need to be considered as 'value'
*
* @param index
* @param value
*/
public void update(int index, long value) {
while (index < treeSize) {
fenwickTree[index] += value;
// Increment the index by the amount up to first significant set bit
// of index
// typically finds the next node to consider
index += index & (-index);
}
}
/**
* @param rightIndex
* @return the sum of the range [0, rightIndex]
*/
public long getPrefixSum(int rightIndex) {
long sum = 0;
while (rightIndex > 0) {
sum += fenwickTree[rightIndex];
// Decrement the index by the amount up to first significant set bit
// of index
// typically finds the parent node to consider
rightIndex -= rightIndex & (-rightIndex);
}
return sum;
}
/**
* (rightIndex >= leftIndex) required
*
* @param leftIndex
* @param rightIndex
* @return the sum of the range [leftIndex, rightIndex]
*/
public long getRangeSum(int leftIndex, int rightIndex) {
return getPrefixSum(rightIndex) - getPrefixSum(leftIndex - 1);
}
/**
* @return actual size of the tree
*/
public int size() {
return fenwickTree.length - 1;
}
}
With a little help from the above implementation we can perform Segment Update Point Queries as well.
/**
* SEGMENT UPDATING, POINT QUERY
*
* for calculating cumulative sums and track segment update
*
* NOTE: 1-based indexing
*
* FenwickTreeSUPQ bit = new FenwickTreeSUPQ(10);
* bit.updateRange(3, 7, 1); // [0, 0, 1, 1, 1, 1, 1, 0, 0, 0]
* bit.updateRange(1, 10, -1); // [-1, -1, 0, 0, 0, 0, 0, -1, -1, -1]
* bit.updateRange(4, 8, 5); // [-1, -1, 0, 5, 5, 5, 5, 4, -1, -1]
*
* bit.getPointValue(3); // 0
* bit.getPointValue(7); // 5
* bit.getPointValue(10); // -1
*
* @author vnbandara
*
*/
class FenwickTreeSUPQ extends FenwickTree {
private int size;
public FenwickTreeSUPQ(int size) {
//we are updating (rightIndex + 1), so treeSize needs to be
//more than that. When initializing the FenwickTree, pass size
//as (original size + 1)
super(size + 1);
this.size = size;
}
/**
* @param leftIndex
* @param rightIndex
* @param value
*/
public void updateRange(int leftIndex, int rightIndex, long value) {
update(leftIndex, value);
update(rightIndex + 1, -value);
}
/**
* point value will be the cumulative sum of all the elements before that
* point (inclusive)
*
* @param index
* @return
*/
public long getPointValue(int index) {
return getPrefixSum(index);
}
/**
* @return the updated array by calculating cumulative sums
*/
public long[] getUpdatedArray() {
long[] array = new long[size];
for (int i = 1; i <= size; i++) {
array[i - 1] = getPointValue(i);
}
return array;
}
}
And when we want to perform Segment Update Segment Queries we can use two FenwickTrees like below
/**
* Use two Fenwick trees to track segment updates and segment sum queries
*
* we are using and considering 1 based indexing
*
* @author vnbandara
*
*/
public class FenwickTreeSUSQ {
private FenwickTree bit1;
private FenwickTree bit2;
private int size;
public FenwickTreeSUSQ(int size) {
this.size = size;
// size + 1 ; because then we can use 1 based indexing
// so the bit1 and bit2 will be (size+2) in size. (1 extra for 1-based
// indexing and another for storing cumulative sums)
bit1 = new FenwickTree(size + 1);
bit2 = new FenwickTree(size + 1);
}
public void updateReange(int leftIndex, int rightIndex, long value) {
bit1.update(leftIndex, value);
bit1.update(rightIndex + 1, -value);
bit2.update(leftIndex, value * (leftIndex - 1));
bit2.update(rightIndex + 1, -value * rightIndex);
}
/**
* @param rightIndex
* @return the sum of elements in range [0, rightIndex] in original array
*/
public long getPrefixSum(int rightIndex) {
return bit1.getPrefixSum(rightIndex) * rightIndex
- bit2.getPrefixSum(rightIndex);
}
/**
* get the sum of all the values in the range [leftIndex, rightIndex] in the
* updated array
*
* ex:
* FenwickTreeSUSQ fen = new FenwickTreeSUSQ(10);
* fen.updateReange(3, 7, 2);
* fen.updateReange(5, 9, 3);
*
* will results : [0, 0, 2, 2, 5, 5, 5, 3, 3, 0] NOTE 1-based indexing
*
* fen.getRangeSum(5, 7) -> 15
* fen.getRangeSum(4, 7) -> 17
* fen.getRangeSum(5, 8) -> 18
*
* @param leftIndex
* @param rightIndex
* @return sum of all the values in the range [leftIndex, rightIndex] in the updated array
*/
public long getRangeSum(int leftIndex, int rightIndex) {
return getPrefixSum(rightIndex) - getPrefixSum(leftIndex - 1);
}
public long getPointValue(int index) {
return getPrefixSum(index);
}
/**
* Just to look-up how original array get updated
*
* ex:
* FenwickTreeSUSQ fen = new FenwickTreeSUSQ(10);
* fen.updateReange(3, 7, 2);
* fen.updateReange(5, 9, 3);
*
* will results : [0, 0, 2, 2, 5, 5, 5, 3, 3, 0] NOTE 1-based indexing
*
* @return
*/
public long[] getUpdatedArray() {
long[] array = new long[size];
for (int i = 1; i <= size; i++) {
array[i - 1] = getPointValue(i) - getPointValue(i - 1);
}
return array;
}
}
Some useful resources,
- https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/FenwickTree.java
- https://discuss.leetcode.com/topic/31599/java-using-binary-indexed-tree-with-clear-explanation
- http://algs4.cs.princeton.edu/99misc/FenwickTree.java.html
- http://www.geeksforgeeks.org/binary-indexed-tree-range-update-range-queries/
- http://cs.stackexchange.com/questions/33014/range-update-range-query-with-binary-indexed-trees
- http://stackoverflow.com/questions/27875691/need-a-clear-explanation-of-range-updates-and-range-queries-binary-indexed-tree/27877427#27877427
0 comments:
Post a Comment