Skip to content

🏆 CP.08: Cây Phân Đoạn (Segment Tree) & Cây Fenwick (BIT) ​

> Cấu trúc dữ liệu quyền lực nhất: Khi một bài toán đòi hỏi vừa cập nhật giá trị phần tử vừa truy vấn tổng/min/max trên đoạn $[L, R]$ liên tục hàng trăm nghìn lần, mảng cộng dồn thông thường sẽ thất bại vì thao tác cập nhật mất $O(N)$. Cây Fenwick và Segment Tree giải quyết cả hai thao tác này chỉ trong $O(\log N)$!


1. Cây Fenwick (Binary Indexed Tree - BIT) Siêu Gọn Nhẹ ​

Cây Fenwick chỉ mất 10 dòng code nhưng giải quyết bài toán:

  • Thêm giá trị $val$ vào vị trí $idx$: add(idx, val) trong $O(\log N)$.
  • Tính tổng tiền tố từ $1$ đến $idx$: query(idx) trong $O(\log N)$.
  • Tính tổng đoạn $[L, R]$ trong $O(\log N)$: query(R) - query(L - 1).
cpp
#include <vector>
#include <iostream>

using namespace std;
using ll = long long;

struct FenwickTree {
    int n;
    vector<ll> tree;

    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    // Cộng thêm 'delta' vào vị trí 'idx' (chỉ số tính từ 1)
    void add(int idx, ll delta) {
        for (; idx <= n; idx += idx & -idx) { // Phép bù 2 lấy bit 1 thấp nhất
            tree[idx] += delta;
        }
    }

    // Tính tổng từ 1 đến idx
    ll query(int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }

    // Truy vấn tổng đoạn [l, r]
    ll query_range(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    FenwickTree ft(5);
    ft.add(1, 3);
    ft.add(2, 5);
    ft.add(3, 2);
    ft.add(4, 8);
    ft.add(5, 1);

    cout << "Tong doan [2, 4]: " << ft.query_range(2, 4) << '\n'; // 5 + 2 + 8 = 15

    ft.add(3, 10); // Tăng phần tử thứ 3 thêm 10
    cout << "Tong doan [2, 4] sau khi cap nhat: " << ft.query_range(2, 4) << '\n'; // 25

    return 0;
}

2. Cây Phân Đoạn (Segment Tree) Đa Năng ​

Segment Tree mạnh hơn Fenwick vì nó có thể xử lý hầu như mọi phép toán kết hợp: tổng, tìm giá trị nhỏ nhất (RMQ - Range Minimum Query), tìm giá trị lớn nhất, GCD, v.v.

mermaid
flowchart TD
    Root["Đoạn [1, 4]"] --> Left["Đoạn [1, 2]"]
    Root --> Right["Đoạn [3, 4]"]
    Left --> L1["Phần tử [1, 1]"]
    Left --> L2["Phần tử [2, 2]"]
    Right --> R1["Phần tử [3, 3]"]
    Right --> R2["Phần tử [4, 4]"]

Triển khai Segment Tree tìm Min trên đoạn (Point Update, Range Query): ​

cpp
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int INF = 1e9 + 7;

struct SegmentTree {
    int n;
    vector<int> st;

    SegmentTree(int n) : n(n), st(4 * n, INF) {}

    // Xây dựng cây từ mảng ban đầu
    void build(const vector<int>& a, int id, int l, int r) {
        if (l == r) {
            st[id] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, 2 * id, l, mid);
        build(a, 2 * id + 1, mid + 1, r);
        st[id] = min(st[2 * id], st[2 * id + 1]);
    }

    // Cập nhật vị trí 'pos' thành giá trị 'val'
    void update(int id, int l, int r, int pos, int val) {
        if (l == r) {
            st[id] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2 * id, l, mid, pos, val);
        else update(2 * id + 1, mid + 1, r, pos, val);
        st[id] = min(st[2 * id], st[2 * id + 1]);
    }

    // Truy vấn giá trị nhỏ nhất trên đoạn [u, v]
    int query_min(int id, int l, int r, int u, int v) {
        if (v < l || r < u) return INF; // Ngoài phạm vi
        if (u <= l && r <= v) return st[id]; // Nằm trọn trong phạm vi
        int mid = (l + r) / 2;
        return min(query_min(2 * id, l, mid, u, v),
                   query_min(2 * id + 1, mid + 1, r, u, v));
    }
};

3. Bảng So Sánh Nhanh: Khi Nào Dùng Gì? ​

Tiêu chíMảng Cộng Dồn (Prefix Sum)Cây Fenwick (BIT)Cây Phân Đoạn (Segment Tree)
Độ dài code3 dòng10 dòng30 - 50 dòng
Bộ nhớ$1 \times N$$1 \times N$$4 \times N$
Cập nhật$O(N)$ (Rất chậm)$O(\log N)$$O(\log N)$ (Hỗ trợ cả Lazy Update)
Truy vấn$O(1)$$O(\log N)$$O(\log N)$
Khi nào dùng?Mảng tĩnh KHÔNG thay đổi giá trịCần tính tổng, nghịch thế, mảng biến độngTìm Min/Max, GCD, cập nhật cả đoạn