Concepts13
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.
Mo's Algorithm - With Updates
Mo's algorithm with updates treats array modifications as a third dimension called time and answers range queries on the correct version of the array.
Mo's Algorithm
Mo's algorithm answers many range queries offline by reordering them to minimize pointer movement along the array.
Rectangle Union Area
The union area of many axis-aligned rectangles can be computed efficiently using a sweep line over x and a segment tree tracking covered y-length.
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.
Wavelet Tree
A wavelet tree is a recursive data structure built over a sequenceβs alphabet that answers rank, select, and quantile (k-th smallest) queries in O(log Ο) time, where Ο is the number of distinct values.
Persistent Segment Tree
A persistent segment tree stores every historical version of an array-like data while supporting queries and updates in O(log n) time.
Merge Sort Tree
A Merge Sort Tree is a segment tree where every node stores the sorted list of values in its segment.
2D Fenwick Tree
A 2D Fenwick Tree (Binary Indexed Tree) supports point updates and rectangle sum queries in O(log n Γ log m) time.