EnderShadow8·4 yıl önce·discussSegment trees are the foundation upon which all of competitive programming is built.
EnderShadow8·4 yıl önce·discussSegment trees are objectively superior in all ways except implementation length
EnderShadow8·4 yıl önce·discussTreap: https://en.wikipedia.org/wiki/TreapIt'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.htmlLike 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.