6 ms·
Treap: https://en.wikipedia.org/wiki/Treap https://en.wikipedia.org/wiki/Treap It's like a Red-Black tree in use case, but much faster to implement, which is g
by EnderShadow8 4y ago
Treap: https://en.wikipedia.org/wiki/Treap https://en.wikipedia.org/wiki/Treap
It's like a Red-Black tree in use case, but much faster to implement, which is good for competitive programming. The average case complexity is the same for all operations, but there's an unlikely degeneration to worst-case linked-list behaviour.
Lazy Propagation Segment Tree: https://cp-algorithms.com/data_structures/segment_tree.html https://cp-algorithms.com/data_structures/segment_tree.html
Like a segment tree in that it supports range queries in logarithmic time, but supports range updates in log time as well.
I know a few more fun ones that I occasionally use in contests, but I've never touched otherwise.
- cassepipe 4y agoSpeaking of ease of implementation, I just discovered AA trees. They are probably not "obscure" but I think they are worthy of more fame because they perform jsut as well as red-black trees and are easier to implement. Finding clear comprehensive documentation about them was not easy though, so here is for you, the best I could find : https://www.cs.umd.edu/class/fall2019/cmsc420-0201/Lects/lect06-aa.pdf https://www.cs.umd.edu/class/fall2019/cmsc420-0201/Lects/lec... And the, unhelpful to me, orginal paper : https://user.it.uu.se/~arnea/ps/simp.pdf https://user.it.uu.se/~arnea/ps/simp.pdf
- kgr 4y agoThe Wikipedia article on AA-Trees is good: https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree
- _benedict 4y agoThe nicest thing about treaps is how easy union/intersection/disjunction are.