Contrived Use Case
Imagine that we are creating an analytics tool for a financials brokerage, where orders are coming in all the time. Let’s say we’re interested in knowing how many orders fall between a certain value (a range query), in real-time. Lets say that orders can fall between $0.01 and $5M, and we want to let our clients query at any given time how many orders have gone through so far that fall between any $x and $y.
A fairly simple implementation of this would just mark down the price of each incoming order in a price array / container, and when a range query comes through we would do a simple iteration from $x to $y and sum the range together. If we want to find the range of orders that fall between $9.49 and $250 Thousand, we have to iterate from 949 pennies to 25 Million pennies (Since our data precision is to the penny), this can become a problem for some even more troublesome range queries. A solution to this is a Fenwick Tree, also known as a Binary Indexed Tree. Using this very clever data structure, we can sum the order price frequency between 949¢ and 25 million ¢ in Log time, which for a range of size 25 Million is almost nothing. Also note: Since new data is coming in all the time, a pre-calculation is not possible (unless you have a method of updating it, which this data structure happens to have as well).
The Algorithm
A Fenwick Tree, also known as a Binary Indexed Tree, allows you to calculate the sum of elements in an array for any given index range in O(Log(N)) time, updates on the array are slowed from O(1) to O(Log(N)). If we chose to go with the standard ‘naive’ implementation we would have O(N) range reads and O(1) writes/updates, calculating the sum for a given index range would involve iterating over every single element in the range and adding them up.
You may be familiar with the fact that any number can be broken down into its constituent powers of two. We want to take advantage of this fact and use it to be able to represent a range by summing several ‘subfrequencies’.
We will be representing our tree in the form of an array, similar to how a heap is implemented but with a completely different indexing scheme. We want to assign each element of this array a range that it is responsible for. Lets say we are interested in finding out the cumulative frequency sum for the range 1..7, there is a very clever way of assigning range responsibilities such that we can use the position of every ’1′ in the binary representation of 7 to find out which parts of the tree are responsible for the ranges we are interested in.
Range responsibilities are assigned as follows:
- Let ctz() represent the position of the last 1 bit in a given number, also known as ‘count trailing zeroes’. ex. ctz(12) = 2, since 12 in binary is 1100b and the last ‘set’ bit is in position 2 (from the right, 0-indexed)
- Index i in our tree/array is responsible for the range (i – 2^ctz(i) , i]
- Our tree array is 1-based, tree[0] does not represent anything.
Examples:
- 7 in binary is 111b, so it is responsible for the range (110b, 111b], or (6,7] … only itself, 7.
- 6 in binary is 110b, so it is responsible for the range (100b, 110b], or (4, 6] … the numbers 5,6
- 4 in binary is 100b, so it is responsible for the range (000b, 100b] or (0, 4] … the numbers 1,2,3,4
- Notice that tree[7] + tree[6] + tree[4] = cumulative frequency sum of 1..7, and that we acquired this by continuously getting rid of the last set bit in our binary representation.
Such a responsibility tree ends up looking like this (With how the range 1..7 is interpreted):
Tree of responsibilities
Given this sort of tree structure here’s how we would implement finding the cumulative frequency sum between x and y. Notice we can only find ranges starting at 1, so we take the difference between 2 ranges. To find the range between 10000 and 20000 with the following code: read(20000) – read(10000).
int read(int idx) {
int sum = 0;
while (idx > 0){
sum += tree[idx];
idx -= (1 << ctz(idx));
}
return sum;
}
Note: (1 << ctz(idx)) can be greatly optimized, what we’re really doing in that line is removing the least sig figure in idx.
Updating The Tree
Remember that we still have to be able to increment certain price frequencies as they come in, so we need the ability to update this tree. Lets say an order comes in for $25.50, we want to increment the frequency of 2550 in our tree by 1. This means we need to visit every single index whose responsibility range contains 2550 and increment its value by 1. (Or to put it in terms of the graph above, every index whose responsibility bar covers 2550.) Every index whose responsibility range contains 2550 is greater than 2550 (and 2550 itself).
We want to find the very next index greater than 2550 which whose responsibility range also contains 2550, increment its value by 1 and then repeat. Since the number 2550 is just too large to explain an example with, lets assume we’re working with the number 1. If you inspect the table below, you’ll notice that range size of a number is dependent specifically on it’s ctz() value. Also, notice the path that we follow to update the value for 1, we continue to higher values who have higher ctz, we find the next value by adding (1 << ctz(i)).
Responsibility Tree – CTZ Columns
The code to update the tree is very similar to reading the tree:
Note: We stop going up the tree once we go beyond our maximum, which in our contrived example would be 5 Million dollars worth of pennies.
void update(int idx ,int val){
while (idx <= MaxVal){
tree[idx] += val;
idx += (1 << ctz(idx));
}
}
So that’s it, now you can read and update a Fenwick tree. Surprisingly the total lines of code is ~15.
If you found this article interesting/cool, go ahead and share or like it on your favorite social network!
Other article in this series: Adversary Discovery
Sources:
Original Research Paper
Topcoder
