Concepts48
Category
Rollback DSU
Rollback DSU (Disjoint Set Union with undo) lets you union sets and later revert to any previous state in LIFO order.
DSU with Weighted Edges
A DSU with weighted edges (also called a potential or difference-constraint union-find) maintains relative values between elements while still supporting near-constant-time merges and finds.
Disjoint Set Union (Union-Find)
Disjoint Set Union (Union-Find) maintains a collection of non-overlapping sets and supports fast merging and membership queries.
Policy-Based Data Structures
Policy-Based Data Structures (PBDS) are GNU C++ extensions that add advanced containers like an order-statistics tree, a fast hash table, and ropes for efficient string edits.
Hash Table
A hash table stores key–value pairs and finds items in expected O(1) time using a hash function to map keys to buckets.
Ordered Set and Map
std::set and std::map store elements in sorted order using a balanced binary search tree (typically a Red-Black Tree).
Priority Queue (Heap)
A priority queue returns the highest-priority element first and is efficiently implemented by a binary heap.
Queue and Deque
A queue is a First-In-First-Out (FIFO) line where you add at the back and remove from the front in O(1) time.
Monotonic Deque
A monotonic deque is a double-ended queue that keeps elements in increasing or decreasing order so that the front always holds the current optimum (min or max).
Stack
A stack is a Last-In, First-Out (LIFO) data structure where push, pop, and top operations run in O(1) time.
Array and Vector
Arrays and vectors store elements contiguously, giving O(1) random access via index.
Monotonic Stack
A monotonic stack is a stack that keeps its elements in increasing or decreasing order to answer range queries in linear time.