Concepts6
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.