Chapter 2: Data Structures

Data structures are what separate "I know the algorithm" from "I can solve it fast enough." This chapter is the point where the notebook shifts from ideas to machinery: basic containers, then the competitive-programming workhorses like DSU, Fenwick trees, and segment trees, and finally the specialized tools for rollback, split/merge, and line queries. The common theme is simple: replace repeated O(n) scans with an invariant you can maintain in O(log n) or O(1).

Coming from: Chapter 1 — Essential Techniques — the techniques that tell you what to compute Going to: Chapter 3 — Graph Foundations — the traversal and shortest-path tools that tell you how to move through relationships Bridge: BRIDGE-to-graphs.md — the conceptual handoff between the two

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	Stack, Queue, and Deque	Beginner	"Process in LIFO/FIFO order"
02	Linked List Basics	Beginner	"Insert/delete in O(1) at known position"
03	Linked Lists in Contests	Beginner	"Simulate deletions in a sequence"
04	Monotonic Stack	Intermediate	"Next greater/smaller element"
05	Monotonic Queue	Intermediate	"Sliding window min/max"
06	Hash Map and Unordered Map	Beginner	"Count occurrences" or "O(1) lookup"
07	Tree Basics	Beginner	"Rooted tree traversal"
08	Set and Multiset	Beginner	"Ordered container with O(log n) insert/find"
09	Priority Queue and Heaps	Beginner	"Repeatedly extract minimum" (Dijkstra, greedy)
10	Policy-Based DS (PBDS)	Intermediate	"Kth smallest" or "count elements < X"
11	Union-Find (DSU)	Intermediate	"Are u and v connected?" + edges added online
12	Sparse Table (RMQ)	Intermediate	"Static range min/max" with no updates
13	Binary Indexed Tree (Fenwick)	Intermediate	"Prefix sums" + "point updates"
14	2D Fenwick Tree	Advanced	"2D prefix sums with updates"
15	Segment Tree	Intermediate	"Range query" + "point update" (any associative op)
16	Segment Tree with Lazy Propagation	Advanced	"Range query" + "range update"
17	Trie	Intermediate	"Common prefix queries" or "XOR maximization"
18	Cartesian Tree (Treap)	Advanced	"Split/merge sequences" or "implicit array with insert/delete"
20	Li Chao Tree	Advanced	"Add line, query max at x" — online CHT alternative
21	Segment Tree Merging	Advanced	"Merge subtree info during DFS" (dynamic seg tree merge)
19	Persistent DSU	Advanced	"Add/remove edges offline" — rollback-capable union-find

If You Only Read 3 Files

1. Segment Tree — because it's the single most versatile data structure in competitive programming. Range queries + point updates for any associative operation. Learn this and you can solve hundreds of problems.
2. Union-Find (DSU) — because connectivity queries appear constantly in graph problems, and DSU answers them in near-O(1). Also the backbone of Kruskal's MST algorithm.
3. Monotonic Stack — because "next greater element" is a pattern that shows up in disguise across many problems, and the monotonic stack technique is elegant, short, and easy to get wrong if you haven't practiced it.

Cross-Chapter Connections

• Union-Find (DSU) is essential for MST — Kruskal in Chapter 3
• Segment Tree powers Euler Tour queries and Heavy-Light Decomposition in Chapter 6
• Segment Tree with Lazy is needed for Sweep Line problems in Chapter 9
• Trie extends into Aho-Corasick for multi-pattern matching in Chapter 5
• Priority Queue is used directly in Dijkstra's Algorithm in Chapter 3
• Not sure which structure to pick? See the Data Structure Selection Guide in Chapter 11

---

File Listing

File	Topic	Level
stack-queue-deque	Stack, Queue, and Deque	⭐
linked-list-basics	Linked List Basics	⭐
linked-list-contest	Linked Lists in Contests	⭐
hash-map-and-unordered-map	Hash Map and Unordered Map	⭐
set-and-multiset	Set and Multiset	⭐
priority-queue-and-heaps	Priority Queue and Heaps	⭐
tree-basics	Tree Basics	⭐
monotonic-stack	Monotonic Stack	⭐⭐
monotonic-queue	Monotonic Queue	⭐⭐
union-find-dsu	Union-Find (DSU)	⭐⭐
binary-indexed-tree-fenwick	Binary Indexed Tree (Fenwick)	⭐⭐
segment-tree	Segment Tree	⭐⭐
sparse-table-rmq	Sparse Table (RMQ)	⭐⭐
trie	Trie	⭐⭐
policy-based-ds	Policy-Based Data Structures (PBDS)	⭐⭐
segment-tree-lazy	Segment Tree with Lazy Propagation	⭐⭐⭐
binary-indexed-tree-2d	2D Fenwick Tree	⭐⭐⭐
cartesian-tree	Cartesian Tree (Treap)	⭐⭐⭐
lichao-tree	Li Chao Tree	⭐⭐⭐
segment-tree-merge	Segment Tree Merging	⭐⭐⭐
persistent-dsu	Persistent DSU (Rollback)	⭐⭐⭐

Suggested Reading Order

1. Stack, Queue, and Deque — foundational restricted-access containers
2. Hash Map and Unordered Map — O(1) lookups for counting and indexing
3. Set and Multiset — ordered containers with O(log n) operations
4. Priority Queue and Heaps — extract min/max for Dijkstra and greedy
5. Tree Basics — representation and traversal fundamentals
6. Monotonic Stack — next greater/smaller element patterns
7. Monotonic Queue — sliding window min/max in O(1)
8. Union-Find (DSU) — near-constant connectivity queries
9. Binary Indexed Tree (Fenwick) — prefix sums with point updates
10. Segment Tree — general range queries and point updates
11. Sparse Table (RMQ) — O(1) static range minimum queries
12. Trie — prefix-based string lookups
13. Policy-Based DS (PBDS) — order statistics with GNU PBDS
14. Segment Tree with Lazy Propagation — range updates with lazy propagation
15. 2D Fenwick Tree — extend Fenwick to 2D grids
16. Cartesian Tree (Treap) — implicit treap with split/merge
17. Li Chao Tree — online "add line, query max at x" structure
18. Segment Tree Merging — merge dynamic seg trees during DFS
19. Persistent DSU — rollback-capable union-find for offline dynamic connectivity