Concepts22
Category
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.
Monotonic Stack
A monotonic stack is a stack that keeps its elements in increasing or decreasing order to answer range queries in linear time.