Concepts6
Sqrt Tree
A sqrt tree is a layered block-decomposition data structure that answers range queries in O(1) time after O(n \log \log n) preprocessing.
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.
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 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).
Monotonic Deque
A monotonic deque is a double-ended queue that keeps elements in increasing or decreasing order so that the front always holds the current optimum (min or max).