Chuyển tới nội dung chính

Segment tree & Fenwick (nâng cao)

Bạn sẽ học được gì

Một bài hay gặp: "tính tổng đoạn [a, b]" và "cập nhật một phần tử" — liên tục, xen kẽ. Segment tree và Fenwick (BIT) làm cả hai trong O(log n). (Bài giới thiệu — hiểu khi nào cần và ý tưởng, chưa cần thuộc cài đặt.)

1. Vì sao mảng thường không đủ?​

Xét hai nhu cầu trên một mảng: truy vấn tổng đoạn [a, b] và cập nhật một phần tử. Các cách quen thuộc đều lệch:

CáchTruy vấn tổng [a,b]Cập nhật 1 phần tử
Mảng thườngO(n) (cộng từng phần tử)O(1)
Mảng tiền tố (prefix sum)O(1)O(n) (phải tính lại tiền tố)
Segment tree / FenwickO(log n)O(log n)

Nếu chỉ truy vấn (không cập nhật) → prefix sum là đủ và đơn giản nhất. Nhưng nếu vừa truy vấn vừa cập nhật xen kẽ → cần segment tree / Fenwick để cả hai cùng nhanh.

2. Ý tưởng segment tree: cây tổng từng đoạn​

Mỗi nút lưu tổng của một đoạn mảng. Gốc lưu tổng cả mảng; chia đôi xuống dưới; lá là từng phần tử. Tổng [a,b] = ghép vài nút phủ đúng đoạn đó (~log n nút).

                 [0..3]=10           ← tổng cả mảng
                /        \
          [0..1]=3      [2..3]=7
           /   \         /   \
        [0]=1 [1]=2   [2]=3 [3]=4    ← lá = phần tử
        (mảng gốc: [1, 2, 3, 4])
  • Truy vấn [a,b]: đi xuống, gộp các nút phủ đoạn → O(log n).
  • Cập nhật A[i]: sửa lá rồi cập nhật các nút cha trên đường lên → O(log n).

3. Fenwick tree (BIT) — gọn hơn cho tổng tiền tố​

Fenwick (Binary Indexed Tree) là cấu trúc gọn hơn, code ngắn, chuyên cho tổng tiền tố với cập nhật điểm — cũng O(log n) cả hai, ít bộ nhớ hơn segment tree. Mẹo của nó dựa trên biểu diễn nhị phân của chỉ số. (Chi tiết để dành khi bạn cần — ở mức này chỉ cần biết nó tồn tại và làm gì.)

4. So sánh nhanh​

Prefix sumFenwick (BIT)Segment tree
Truy vấn tổngO(1)O(log n)O(log n)
Cập nhật điểmO(n)O(log n)O(log n)
Linh hoạt (min/max/khoảng)thấpthấp (chủ yếu tổng)cao
Codeđơn giản nhấtgọndài hơn

Quy tắc: chỉ truy vấn → prefix sum. Truy vấn + cập nhật, chỉ cần tổng → Fenwick. Cần linh hoạt (min/max, gán đoạn) → segment tree.

🎬 Trực quan hóa tương tác — VisuAlgo
Trực quan hóa cây segment: xây dựng, truy vấn khoảng, cập nhật điểm từng bước.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

5. Minh họa: vì sao prefix sum đuối khi cập nhật​

Đang tải trình chạy code…

6. Mẫu nhận diện​

  • "Truy vấn tổng/min/max trên đoạn" xen kẽ "cập nhật phần tử" → segment tree / Fenwick.
  • Chỉ truy vấn, không đổi dữ liệu → prefix sum (đơn giản hơn nhiều, đừng dùng segment tree thừa).
  • Đây là chủ đề nâng cao (lập trình thi đấu) — nắm khi nào cần, học cài khi gặp bài thật.

7. 🎮 Trò chơi: Chọn cấu trúc truy vấn khoảng​

🎮 Chọn cấu trúc truy vấn khoảngCâu 1/4· Điểm 0· 🔥 0

Chỉ truy vấn → prefix sum. Truy vấn + cập nhật → Fenwick/segment tree.

Vừa truy vấn tổng đoạn vừa cập nhật phần tử liên tục.

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Segment tree giải bài nào tốt nhất?
2. Nếu mảng KHÔNG đổi và chỉ cần tổng đoạn, nên dùng?
3. Fenwick (BIT) so với segment tree?
📚 Đọc thêm & Luyện tập
🎬 Video
🏋️ Luyện tập
📖 Sách/tài liệu

9. Hoàn thành — XONG Chương 2.5! 🎉​

…

☑️ Hết Chương 2.5 (Cây). Tiếp theo: 2.6.1 — Khái niệm đồ thị.