Data Structures¶
Data structures are fundamental building blocks for efficient algorithm design. This category covers advanced data structures that enable fast queries, updates, and specialized operations essential for solving complex computational problems.
Techniques in This Category¶
| Technique | Description | Link |
|---|---|---|
| Dynamic Arrays | std::vector: growth, reserve, when to use contiguous arrays. |
Dynamic Arrays |
| Sets & Maps | Ordered vs unordered sets/maps; lookup and iteration tradeoffs. | Sets & Maps |
| Iterators & Ranges | begin/end, invalidation, erase–remove idiom. |
Iterators & Ranges |
| Segment Tree / BIT | Range queries and point updates in \(O(\log n)\). | Segment Tree / BIT |
| Lazy Segment Tree | Range updates with lazy propagation on segment trees. | Lazy Segment Tree |
| 2D Segment Tree / BIT | Rectangle queries on matrices; nested structures. | 2D Segment Tree / BIT |
| Heap / Priority Queue | Dynamic min/max; Dijkstra and scheduling. | Heap / Priority Queue |
| Disjoint Set (DSU) | Union–find; connectivity and Kruskal. | Disjoint Set (DSU) |
| Square Root Decomposition | Block-based aggregates; \(O(\sqrt{n})\) updates/queries. | Sqrt Decomposition |
| Mo’s Algorithm | Offline range queries with sqrt reordering. | Mo’s Algorithm |
When to Use Advanced Data Structures¶
These data structures are essential when: - You need to perform frequent range queries or updates - Maintaining extremal elements with dynamic operations - Working with connectivity or union-find problems - Optimizing time complexity for repeated operations
Common Applications¶
Segment Trees & Binary Indexed Trees¶
- Range Sum Queries: Computing sums over ranges efficiently
- Range Minimum/Maximum: Finding extremal values in ranges
- Range Updates: Applying updates to ranges of elements
- Inversion Counting: Counting inversions in arrays
Heaps & Priority Queues¶
- Dijkstra's Algorithm: Finding shortest paths in graphs
- Median Maintenance: Keeping track of running median
- Task Scheduling: Prioritizing tasks based on urgency or importance
- Merge Operations: Efficiently merging sorted sequences
Disjoint Set Union¶
- Connectivity Problems: Determining if elements are connected
- Minimum Spanning Tree: Kruskal's algorithm implementation
- Cycle Detection: Detecting cycles in undirected graphs
- Component Analysis: Analyzing connected components