Concepts8
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.
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.
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.
Dynamic Segment Tree
A dynamic segment tree stores values over a huge coordinate range by creating nodes only when an operation touches their interval.
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).
2D Fenwick Tree
A 2D Fenwick Tree (Binary Indexed Tree) supports point updates and rectangle sum queries in O(log n × log m) time.
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.