Finger-Trees

Basic idea

A persistent functional sequence with cheap access at both ends and $O(\log n)$ split/concat. Generalises to many abstract structures (deques, priority queues, interval maps) via a monoidal annotation.

Key formulas

• push/pop (either end): $O(1)$ amortised
• Concat: $O(\log\min(m, n))$
• Split / index: $O(\log n)$

Resources

• https://andrew.gibiansky.com/blog/haskell/finger-trees/
• https://www.youtube.com/watch?v=ip92VMpf_-A

Siblings

• Adaptive Radix Tree
• Bloom filter
• Cache Oblivious Algorithms & Datastructures
• Count-min sketch
• CTrie
• Disjoint Set
• Fenwick tree
• Fibonacci heaps
• GeoHash
• Hash Array Mapped Tries
• Hash Tables
• Hilbert-R Tree
• HyperLogLog
• Judy Arrays
• k-d Tree
• Links
• M Tree
• Pairing heaps
• R tree
• RRB-Trees
• Segment Trees
• Sparse Sets
• Succint Datastructures