Concepts9
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.
Parallel Binary Search
Parallel Binary Search (PBS) lets you binary-search the answers of many queries at once by batching them by their current mid value.
CDQ Divide and Conquer
CDQ divide and conquer is an offline technique that splits the timeline (or one coordinate) and lets updates from the left half contribute to queries in the right half.
DSU on Tree (Sack)
DSU on Tree (also called the Sack technique) answers many subtree queries in O(n \log n) by keeping data from the heavy child and temporarily re-adding light subtrees.
Line Sweep
Line sweep (plane sweep) is a technique that processes geometric objects by moving an imaginary line and handling events in sorted order.
LIS Variants
LIS variants extend the classic longest increasing subsequence to handle non-decreasing sequences, counting how many LIS exist, and maximizing the sum of a subsequence.
Coordinate Compression
Coordinate compression replaces large, sparse, or arbitrary values with small consecutive integers while preserving relative order.
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.
Fenwick Tree (Binary Indexed Tree)
A Fenwick Tree (Binary Indexed Tree) maintains prefix sums so you can update a single position and query a prefix in O(\log n) time with a tiny constant factor.