Concepts6
Chtholly Tree (ODT - Old Driver Tree)
Chtholly Tree (ODT) stores an array as a set of non-overlapping value-constant intervals and updates by cutting and replacing whole ranges.
Sqrt Decomposition
Sqrt decomposition partitions an array into about \(\sqrt{n}\) blocks, each of size about \(\sqrt{n}\), to speed up range queries and updates.
Segment Tree Beats
Segment Tree Beats is a segment tree variant that supports range chmin/chmax (clamping) together with queries like range sum, min, and max in amortized logarithmic time.
Segment Tree - Handling Multiple Lazy Operations
When a segment tree supports multiple range updates, you must define how lazy tags compose, because the order of operations matters and composition is not commutative.
Segment Tree with Lazy Propagation
A segment tree with lazy propagation supports fast range updates and range queries in O(\log n) time.
Fenwick Tree - Range Update Range Query
A Fenwick Tree (Binary Indexed Tree) can support range additions and range sum queries by maintaining two trees, often called B1 and B2.