4 ms·
Little-Known Awesome Algorithms: Fenwick Range Trees
- chime 14y agoVery clever but replacing O(1) with O(log n) for updates is probably worse than the benefit gained by O(log n) range-sum instead of O(n) when the updates are happening constantly, in real-time - think Twitter Firehose. In practice, it would make a lot more sense to pre-define the buckets and update those when doing insert/update/delete. Even 1m buckets is just 1-4MB of data, depending on how many counts do you want (2^8 - 2^32). That would give you O(1) update and O(k) range-sum where k = number of buckets. You want k to be smaller than n otherwise you're back to the naive implementation.
- randartie 14y agoYou're right, this technique is useful when the ratio of reads to writes is just right!
- psykotic 14y agoFenwick trees were invented for context modeling with arithmetic coding. Reads and writes are perfectly balanced. For every symbol, there's one write to update the model and one read to determine the cumulative probability.
- joe_the_user 14y agoHmm... A Fenwick Binary Indexed Tree allows you to calculate the sum of elements in an array for any given index range in O(Log(N)) time I can modify a B-tree so each branch node keeps track of the sum total of values of nodes under it and the absolute number of nodes under it. It's pretty easy to find the sum of elements within a range, the range of elements that equal a given sum and so-forth. All O(log(n)). Why the weirdo data structure?
- randartie 14y agoThe implementation of that b-tree is actually pretty difficult (I've attempted in the past, but it depends on your skill of course) and the constant factor is much larger. (It's somewhat difficult to implement because when you remove a node, tricky things happen and you need to keep the sub-tree sizes consistent). Granted, whatever floats your boat!
- digitalnalogika 14y agoI used this structure (although I knew it by totally different name) a lot in time constrained contests, the code is very short and easy to implement. Also: idx -= (1 << ctz(idx)); I used to write this as: idx -= idx&-idx;
- joe_the_user 14y agoSure B-trees are hard to write from the ground up but there are plenty of good implementations already the Internet that can be modified. The extra functionality is a simple enough addition to any binary-tree-type data structure that I was annoyed that Boost/Qt didn't have it already included.
- zvrba 14y ago> Sure B-trees are hard to write from the ground up but there are plenty of good implementations already the Internet that can be modified. Care to name some, also having a non-restrictive license? (That excludes GPL).
- joe_the_user 14y agoTry http://www.touc.org/btree.html http://www.touc.org/btree.html This c++ template is fairly simple and I have tested it a reasonable amount.
- utopkara 14y agoObviously, B-trees have many other uses. But, i) Fenwick algorithm is more efficient when it comes to the hard numbers (the k is small), ii) it is very easy to implement.
- chengsun 14y agoThis useful data structure confusingly goes by several different names. Binary indexed tree: https://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees https://community.topcoder.com/tc?module=Static&d1=tutor... Cumulative frequency table (which interestingly enough Simon Tatham claims to have independently invented): http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumul...