4 ms·
Fenwick Trees (which, despite the name, are implemented using an array) allow counting prefix sums AND updating prefix sums in O(log n) time. Very useful when n
by gordaco 4y ago
Fenwick Trees (which, despite the name, are implemented using an array) allow counting prefix sums AND updating prefix sums in O(log n) time. Very useful when n is in the order of millions. I have used them a few times in Project Euler problems.
https://en.wikipedia.org/wiki/Fenwick_tree https://en.wikipedia.org/wiki/Fenwick_tree
- nyanpasu64 4y agoIs it possible to implement a Fenwick tree using a tree, and support quickly adding and removing items as well as quickly shifting the positions of suffixes?
- EnderShadow8 4y agoSegment trees are objectively superior in all ways except implementation length
- almog 4y agoAnother advantage to Fenwick Tree: while it shares asymptotic space complexity with Segment Tree, it has better constant factors, which can be useful in very restricted environments.
- silverlake 4y agoI used fenwick trees in a smart contract because space/time costs money.
- almog 4y agoWas going to mention Fenwick Tree here as well, but since you've already did, I'll just add that this is IMO a great introduction to Fenwick Trees: https://www.youtube.com/watch?v=kPaJfAUwViY https://www.youtube.com/watch?v=kPaJfAUwViY