Binary Indexed Tree or Fenwick Tree is data structure that can efficiently update and calculate the prefix sum. We can use a prefix sum array too for calculating prefix sum but it will have expensive updates as each update will take linear time.
Say we have an input array: [1, 2, 3, 4]. Let's see how we can build, search and update the tree.
1. Build Binary Indexed Tree:
The root node of binary indexed tree will always be 0 and its kind of dummy node so for any array of length n the number of nodes in the tree will be n + 1(root/dummy node).
Why 1, 2, 4 are children of 0 and 3 is children of 2:
Basically in binary indexed tree, an index i is a parent of j if by flipping the least significant set bit in j produce i. If we flip least significant set bit in 3 (11), we will get 2 (10) and if we do the same on 2, we will get 0 so 2 is a parent of 3 and 0 is a parent of 2. Now let's see how we build the tree:
Index 1: 2 ^ 0 + 0 so we will add element from index 0 to length 1 that is input[0...0]
Index 2: 2 ^ 1 + 0 so we will add elements from index 0 to length 2 that is input[0...1]
Index 3: 2 ^ 1 + 2^0 so will add elements from index 2 to length 1 that is input[2...2]
Index 4: 2^2 + 0 so will add elements from index 0 to length 4. That is input[0...3]
You can see in the implementation to efficiently build this tree.
2. Get Sum:
We will just sum all the elements in the path from index to root. Say in the above tree we want to get the sum from [0...2] then for binary indexed tree the index is 3. Now if sum the elements from 3 to 0, it will be tree[3] + tree[2] + tree[0] = 3 + 3 = 6. Now the problem is how to get the parent given a index:
- twosComplement = 2's complement of index;
- andResult = index AND twosComplement
- parent = index - andResult
To get the 2's complement we can do -index as negative numbers are stored in the form of 2's complement.
3. Update value: First we get the difference between the original value at index and the input value. Say we want to update value at index 1 and we want change it to 6. Then our difference is 6 - 2 = 4.
Now we want to add this difference to every index of tree which is impacted by this difference. First index is going to be impacted is index + 1. Now we go and change every next impacted index until the next index is more than the size of the tree array. Here is how we are going to calculate the next index:
- twosComplement = 2's complement of index;
- andResult = index AND twosComplement
- nextIndex = index + andResult
Here is how our updated tree will look like:
That's all!
Implementation in C#:
public class BinaryIndexedTree
{
public BinaryIndexedTree(int[] input)
{
this.originalArray = input;
this.binaryIndexedTreeArray = new int[input.Length + 1];
for (int i = 1; i < binaryIndexedTreeArray.Length; ++i)
{
this.AddValueToBinaryIndexedTree(input[i - 1], i);
}
}
public void UpdateBinaryIndexedTree(int value, int index)
{
if (index >= this.binaryIndexedTreeArray.Length - 1)
{
return;
}
int diff = value - this.originalArray[index];
this.originalArray[index] = value;
index += 1;
this.AddValueToBinaryIndexedTree(diff, index);
}
private void AddValueToBinaryIndexedTree(int value, int index)
{
while (index < this.binaryIndexedTreeArray.Length)
{
this.binaryIndexedTreeArray[index] += value;
index = this.GetNextIndex(index);
}
}
public int GetCumulativeSum(int index)
{
if (index >= this.binaryIndexedTreeArray.Length - 1)
{
index = this.binaryIndexedTreeArray.Length - 2;
}
index = index + 1;
int sum = 0;
while (index > 0)
{
sum += this.binaryIndexedTreeArray[index];
index = this.GetParentIndex(index);
}
return sum;
}
public int GetRangeSum(int start, int end)
{
if (end >= this.binaryIndexedTreeArray.Length - 1)
{
end = this.binaryIndexedTreeArray.Length - 2;
}
return this.GetCumulativeSum(end) - this.GetCumulativeSum(start - 1);
}
private int GetParentIndex(int index)
{
return index - (index & -index);
}
private int GetNextIndex(int index)
{
return index + (index & -index);
}
private int[] binaryIndexedTreeArray;
private int[] originalArray;
}
Complexity: Building tree: O(nlogn), Sum: O(logn), Update: O(logn)
No comments:
Post a Comment