Concepts10
Segment Tree with Range Affine Transformation
A segment tree with lazy propagation can support range updates of the form x → a·x + b (affine transformations) and range-sum queries in O(log n) per operation.
Kinetic Tournament Tree
A kinetic tournament tree maintains the minimum (or maximum) of moving values whose pairwise order can change over time.
Euler Tour Tree
An Euler Tour Tree represents each rooted tree as a DFS open/close sequence so that every subtree is a single contiguous interval.
HLD - Path Queries and Updates
Heavy-Light Decomposition (HLD) breaks a tree into a small number of vertical chains so any path (u,v) becomes O(log n) contiguous segments in an array.
Persistent Segment Tree
A persistent segment tree stores every historical version of an array-like data while supporting queries and updates in O(log n) time.
Merge Sort Tree
A Merge Sort Tree is a segment tree where every node stores the sorted list of values in its segment.
Iterative Segment Tree
An iterative segment tree stores all leaves in tree[n..2n-1] and internal nodes in tree[1..n-1], enabling O(\log n) point updates and range queries without recursion.
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.
Segment Tree Basics
A segment tree is a complete binary tree that stores information about array intervals to answer range queries and support point updates in O(log n).