Cấu trúc dữ liệu

Cấu trúc dữ liệu quyết định bạn truy vấn và cập nhật dữ liệu nhanh đến đâu — chọn đúng cấu trúc thường biến một lời giải $O(N^2)$ thành $O(N\log N)$. Mục này đi từ các cấu trúc nền tảng đến những cấu trúc nâng cao phục vụ truy vấn đoạn và bài toán khó.

Nền tảng

• Mảng & Xâu ký tự — thao tác cơ bản, prefix sum, hai con trỏ trên mảng/xâu.
• Ngăn xếp & Hàng đợi — stack, queue, deque và ứng dụng.
• Đồ thị (danh sách kề, ma trận kề) — hai cách biểu diễn đồ thị và khi nào dùng cái nào.

Cấu trúc thường dùng

• Bảng băm — tra cứu key–value trong $O(1)$ trung bình (unordered_map, dict).
• Disjoint Set Union (DSU) — quản lý các tập rời nhau, gần như $O(1)$; nền của Kruskal và đếm thành phần liên thông.

Cây (nhóm lớn)

• Cây — trang chủ đề gồm nhiều cấu trúc cây: BST, Heap, Fenwick Tree, Segment Tree (và các biến thể bền vững / beats), Treap, Trie, HLD, Centroid Decomposition, Link-Cut Tree... Đây là kho cấu trúc truy vấn đoạn quan trọng nhất.

Truy vấn đoạn & nâng cao

• Sparse Table (RMQ) — truy vấn min/max trên đoạn trong $O(1)$ với mảng tĩnh.
• Monotonic Stack và Deque — duy trì tính đơn điệu để tìm "phần tử lớn/nhỏ hơn gần nhất" và min/max cửa sổ trượt.
• Sqrt Decomposition — chia khối $\sqrt{N}$ cho truy vấn/cập nhật đoạn linh hoạt.
• Mo's Algorithm — xử lý offline nhiều truy vấn đoạn trong $O((N+Q)\sqrt{N})$.
• Bitset Optimization — tăng tốc các phép trên tập bit lên $N/64$ lần.

Gợi ý thứ tự học

Bắt đầu từ nhóm Nền tảng và Cấu trúc thường dùng, sau đó vào nhóm Cây (đặc biệt Fenwick & Segment Tree), rồi mới đến các cấu trúc truy vấn đoạn nâng cao.