Concepts7
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.
Sqrt Decomposition on Queries
Sqrt decomposition on queries (time blocking) processes Q operations in blocks of size about \(\sqrt{Q}\) to balance per-query overhead and rebuild cost.
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.
Implicit Treap
An implicit treap is a randomized balanced binary tree that treats array positions as keys without storing them explicitly.
Treap
A treap is a binary search tree on keys combined with a heap on random priorities, which keeps the tree balanced in expectation.
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.
Dynamic Segment Tree
A dynamic segment tree stores values over a huge coordinate range by creating nodes only when an operation touches their interval.