Giao diện
Advanced Data Structures - Tổng Quan
"Cấu trúc dữ liệu đúng = Performance đúng. Chọn sai = Chậm 1000x." - HPN
The Range Query Problem
Bài toán: Cho array N phần tử, trả lời nhiều queries dạng:
- Range query: Tính sum/min/max của đoạn
[L, R] - Point update: Thay đổi giá trị tại index
i
Naive Approach Analysis
| Operation | Naive Array | Prefix Sum |
|---|---|---|
| Range Query | O(N) | O(1) |
| Point Update | O(1) | O(N) |
❌ THE PROBLEM
- Array: Query chậm O(N)
- Prefix Sum: Update chậm O(N)
Với 100K queries trên 100K elements → Timeout!
Advanced Structures
| Structure | Query | Update | Best for |
|---|---|---|---|
| Segment Tree | O(log N) | O(log N) | General (sum, min, max, gcd) |
| Fenwick Tree (BIT) | O(log N) | O(log N) | Sum queries (simpler) |
| Sparse Table | O(1) | N/A | Static data (no updates) |
When to Use What?
Real-World Applications
| Domain | Use Case | Chi tiết |
|---|---|---|
| Finance | Stock analysis | Min/Max price in time window |
| Gaming | Leaderboard | Dynamic ranking queries |
| Databases | OLAP | Aggregate queries |
| Graphics | Collision detection | 2D range queries |
| Networking | Packet analysis | Traffic in time window |
Roadmap Module
- Segment Tree - General range queries
- Fenwick Tree (BIT) - Simpler sum queries
💡 HPN's Rule
"Sum + Updates → Fenwick Tree (đơn giản hơn). Min/Max hoặc Lazy → Segment Tree."