• i. Sparse Table: $O(1)$ queries on a static array after $O(n\log n)$ preprocessing.
• ii. Range Minimum Query: RMQ on a static array is equivalent to LCA on a tree:
• iii. Fenwick Tree: A Fenwick tree (binary indexed tree) stores partial sums over power-of-two blocks:
• iv. Segment Tree: A segment tree stores an associative aggregate for each of the $O(n)$ canonical segments.
• v. Lazy Propagation: Range updates in $O(\log n)$:
• vi. Dynamic and Persistent Segment Trees: struct DynSeg {
• vii. Segment Tree Beats and Historic Values: Some updates can’t be applied to a whole node in $O(1)$:
• viii. Li Chao and Kinetic Segment Trees: Both maintain sets of lines and answer “best value at $x$”.
• ix. Segment Tree Merging and Splitting: Many dynamic segment trees over the same value range $[0,n)$ share one node pool.
• x. Range Order Statistics and Wavelets: Queries like “$k$-th smallest in $a[l..r)$”, “how many values in $[x,y)$ lie in $a[l..r)$”, predecessor/successor within a range.
• xi. Sqrt Decomposition: Split something (the array, the values, the time line, the set of objects) into  ​-sized pieces so that two different costs balance.
• xii. Mo’s Algorithm: Offline range queries where the window $[L,R)$ can be extended and shrunk by one element in $O(1)$ (or $O(\log )$):
• xiii. Offline and 2D Range Queries: Most “2D” problems (points in rectangles, range queries with a value condition, distinct values in a range) become 1D after sorting by one coordinate and sweeping with a Fenwick tree over the other.
• xiv. Permutation Tree: For a permutation $p$, call a subarray $p[l..r)$ an interval if its values form a contiguous range, i.e.
• xv. Range LIS: Answer “length of the longest strictly increasing subsequence of $a[l..r)$” for many ranges.