Segment Tree (Cây phân đoạn)

Wiki › Cấu trúc dữ liệu › Cây

huunguyen · Cập nhật lần cuối 7, Tháng 4, 2026, 21:44

Segment Tree là cây nhị phân lưu thông tin trên các đoạn của mảng. Mỗi node lưu kết quả tổng hợp (tổng, min, max,...) của một đoạn $[l, r]$ .

Độ phức tạp: $O (\log N)$ cho cả truy vấn và cập nhật. Bộ nhớ $O (4 N)$ .

Cài đặt cơ bản (cập nhật điểm, truy vấn đoạn)

struct SegTree {
    int n;
    vector<long long> tree;

    SegTree(int n) : n(n), tree(4*n, 0) {}

    void build(vector<int>& a, int node, int l, int r) {
        if (l == r) { tree[node] = a[l]; return; }
        int mid = (l + r) / 2;
        build(a, 2*node, l, mid);
        build(a, 2*node+1, mid+1, r);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    void update(int node, int l, int r, int pos, long long val) {
        if (l == r) { tree[node] = val; return; }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2*node, l, mid, pos, val);
        else            update(2*node+1, mid+1, r, pos, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;   // ngoài đoạn
        if (ql <= l && r <= qr) return tree[node];  // trong đoạn hoàn toàn
        int mid = (l + r) / 2;
        return query(2*node, l, mid, ql, qr)
             + query(2*node+1, mid+1, r, ql, qr);
    }
};

// Sử dụng (chỉ số 0-based):
SegTree seg(n);
seg.build(a, 1, 0, n-1);
seg.update(1, 0, n-1, i, val);
long long s = seg.query(1, 0, n-1, l, r);

Lazy Propagation (cập nhật đoạn)

Khi cần cập nhật cả đoạn $[l, r]$ (cộng thêm $v$ , gán $v$ ,...), lazy propagation đưa độ phức tạp về $O (\log N)$ :

Mỗi node lưu thêm lazy — phần chưa đẩy xuống con.
Trước khi đi xuống con, push down lazy.

struct LazySegTree {
    int n;
    vector<long long> tree, lazy;

    LazySegTree(int n) : n(n), tree(4*n, 0), lazy(4*n, 0) {}

    void push_down(int node, int l, int r) {
        if (lazy[node] == 0) return;
        int mid = (l + r) / 2;
        tree[2*node]   += lazy[node] * (mid - l + 1);
        tree[2*node+1] += lazy[node] * (r - mid);
        lazy[2*node]   += lazy[node];
        lazy[2*node+1] += lazy[node];
        lazy[node] = 0;
    }

    // Cộng val vào mọi phần tử trong [ql, qr]
    void update(int node, int l, int r, int ql, int qr, long long val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[node] += val * (r - l + 1);
            lazy[node] += val;
            return;
        }
        push_down(node, l, r);
        int mid = (l + r) / 2;
        update(2*node, l, mid, ql, qr, val);
        update(2*node+1, mid+1, r, ql, qr, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        push_down(node, l, r);
        int mid = (l + r) / 2;
        return query(2*node, l, mid, ql, qr)
             + query(2*node+1, mid+1, r, ql, qr);
    }
};

Thay đổi hàm kết hợp

Segment Tree có thể hỗ trợ nhiều loại truy vấn chỉ bằng cách thay hàm kết hợp:

// Min / Max thay vì tổng:
tree[node] = min(tree[2*node], tree[2*node+1]);
// Giá trị trả về khi ngoài đoạn: LLONG_MAX (cho min), LLONG_MIN (cho max)

// GCD:
tree[node] = __gcd(tree[2*node], tree[2*node+1]);
// Giá trị trả về khi ngoài đoạn: 0

Khi nào dùng Segment Tree thay Fenwick Tree?

Cần truy vấn min hoặc max (Fenwick không hỗ trợ)
Cần lazy propagation với logic phức tạp (gán giá trị, kết hợp nhiều loại cập nhật)
Cần lưu thêm nhiều thông tin trên mỗi node

Bài tập minh họa

Truy vấn — point update, range max query

Bình luận

Không có bình luận tại thời điểm này.