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

Segment Tree (cây phân đoạn) là cấu trúc dữ liệu cho phép vừa truy vấn thông tin trên một đoạn $[l,r]$ của mảng (tổng, min, max, gcd...) vừa cập nhật phần tử — cả hai chỉ trong $O(\log N)$.

Bài toán điển hình: cho mảng $N$ phần tử, xử lý $Q$ truy vấn xen kẽ kiểu "tổng đoạn $[l,r]$" và "gán $a[i]=v$". Cách ngây thơ duyệt lại đoạn mỗi truy vấn mất $O(N)$ mỗi lần, tổng $O(NQ)$ — quá chậm khi $N,Q\approx {10}^5$. Tiền tố cộng dồn (prefix sum) trả lời tổng đoạn trong $O(1)$ nhưng cập nhật một phần tử lại tốn $O(N)$. Segment Tree cân bằng cả hai về $O(\log N)$, và còn hỗ trợ những phép mà prefix sum chiều được (min/max/gcd).

Ý tưởng / Trực giác

Ý tưởng cốt lõi: chia để trị trên đoạn. Ta đệ quy chia đoạn $[0,N-1]$ làm đôi, mỗi nửa lại chia đôi, cho tới các đoạn đơn lẻ $[i,i]$. Mỗi đoạn ứng với một node của cây nhị phân; node cha lưu kết quả tổng hợp của hai node con.

Tại sao truy vấn nhanh? Mấu chốt là: bất kỳ đoạn $[ql,qr]$ nào cũng phân rã được thành $O(\log N)$ đoạn chuẩn (các node đã có sẵn trong cây). Khi truy vấn, ở mỗi node ta xét 3 khả năng:

1. Đoạn node nằm hoàn toàn trong $[ql,qr]$ → trả luôn giá trị đã lưu, không đi sâu thêm.
2. Đoạn node không giao với $[ql,qr]$ → trả phần tử trung tính (0 cho tổng, $+\infty$ cho min) rồi dừng.
3. Đoạn node giao một phần → đệ quy xuống cả hai con và gộp kết quả.

Vì chỉ có khoảng 2 node "giao một phần" trên mỗi tầng (một ở biên trái, một ở biên phải), số node thực sự được ghé thăm là $O(\log N)$.

Tại sao cập nhật nhanh? Một phần tử $a[i]$ chỉ thuộc đúng một node ở mỗi tầng — đường đi từ gốc xuống lá $[i,i]$. Sửa lá rồi đi ngược lên cập nhật lại tổng các tổ tiên: chỉ $O(\log N)$ node.

Điều kiện để Segment Tree áp dụng được: phép gộp phải kết hợp (associative). Tức là $f(f(a,b),c)=f(a,f(b,c))$. Tổng, min, max, gcd, "tổng đoạn con lớn nhất"... đều thỏa; nhờ vậy việc ghép kết quả từ nhiều đoạn con cho ra đáp án đúng bất kể thứ tự ghép.

Ví dụ chạy tay

Xét mảng $a=[3,1,2,4]$ (chỉ số 0..3), phép gộp là tổng. Cây phân đoạn (số trong ngoặc là tổng của node):

                 [0,3]=(10)
                /          \
          [0,1]=(4)       [2,3]=(6)
          /     \          /     \
    [0,0]=3  [1,1]=1  [2,2]=2  [3,3]=4

Truy vấn tổng đoạn $[1,3]$ (tức $1+2+4=7$). Đi từ gốc:

[0,3]: [1,3] giao một phần [0,3]  -> xuống 2 con
 ├─ [0,1]: [1,3] giao một phần   -> xuống 2 con
 │   ├─ [0,0]: không giao [1,3]  -> trả 0        <-- dừng
 │   └─ [1,1]: nằm trong [1,3]   -> trả 1        <-- dừng
 └─ [2,3]: NẰM TRỌN trong [1,3]  -> trả 6        <-- dừng, không đi sâu!

Cộng lại: $0+1+6=7$. Đoạn $[1,3]$ được phân rã thành đúng 2 node chuẩn $\{[1,1],[2,3]\}$ — không phải duyệt từng phần tử.

Cập nhật $a[2]=5$ (trước là 2). Đi xuống lá $[2,2]$, sửa rồi cập nhật ngược lên:

[0,3]=(10->13)          (chỉ các node trên đường đi đổi)
        \
       [2,3]=(6->9)
        /
   [2,2]=(2->5)   <-- sửa lá trước

Chỉ 3 node trên đường gốc→lá được cập nhật: lá $[2,2]$ thành 5, rồi $[2,3]$ thành $5+4=9$, rồi gốc thành $4+9=13$. Các node $[0,1],[0,0],[1,1]$ không đổi.

Cài đặt

Cập nhật điểm, truy vấn đoạn

Mảng tree lưu cây theo cách đánh số đống (heap): node $1$ là gốc, hai con của node $v$ là $2v$ và $2v+1$. Cấp phát kích thước $4N$ là an toàn (xem mục Độ phức tạp).

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

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

    // Xây cây từ mảng a, node phụ trách đoạn [l, r]
    void build(vector<int>& a, int node, int l, int r) {
        if (l == r) { tree[node] = a[l]; return; }  // lá: chứa đúng a[l]
        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]; // gộp từ 2 con
    }

    // Gán a[pos] = val
    void update(int node, int l, int r, int pos, long long val) {
        if (l == r) { tree[node] = val; return; }       // tới lá thì gán
        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]; // cập nhật ngược lên
    }

    // Tổng đoạn [ql, qr]
    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;             // không giao -> phần tử trung tính
        if (ql <= l && r <= qr) return tree[node];  // node nằm trọn trong [ql,qr]
        int mid = (l + r) / 2;
        return query(2 * node,     l,     mid, ql, qr)
             + query(2 * node + 1, mid + 1, r,  ql, qr);
    }
};

// Cách dùng (chỉ số 0-based, gốc là node 1, đoạn toàn cục [0, n-1]):
// 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);

Đổi phép gộp

Chỉ cần thay phép cộng và phần tử trung tính (giá trị trả về khi "không giao"):

// Min:  tree[node] = min(tree[2*node], tree[2*node+1]);
//       không giao -> trả LLONG_MAX
// Max:  tree[node] = max(tree[2*node], tree[2*node+1]);
//       không giao -> trả LLONG_MIN
// GCD:  tree[node] = __gcd(tree[2*node], tree[2*node+1]);
//       không giao -> trả 0

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

Khi cần cập nhật cả đoạn $[ql,qr]$ (cộng thêm $v$ cho mọi phần tử, hay gán...), nếu đi xuống từng lá thì một cập nhật đoạn tốn $O(N)$. Lazy propagation giữ lại độ phức tạp $O(\log N)$ bằng mẹo: khi một node nằm trọn trong đoạn cập nhật, ta cập nhật giá trị tổng hợp của node đó ngay và ghi nợ (lazy) phần thay đổi cho các con — chỉ "đẩy nợ" xuống (push down) khi thực sự cần đi qua node đó.

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

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

    // Đẩy "nợ" của node xuống 2 con trước khi đi tiếp
    void push_down(int node, int l, int r) {
        if (lazy[node] == 0) return;
        int mid = (l + r) / 2;
        // mỗi con cộng lazy * (số phần tử của con)
        tree[2 * node]     += lazy[node] * (mid - l + 1);
        tree[2 * node + 1] += lazy[node] * (r - mid);
        lazy[2 * node]     += lazy[node];   // dồn nợ tiếp cho cháu
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;                     // node đã trả hết nợ
    }

    // Cộng val cho 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) {           // node nằm trọn -> ghi nợ, dừng
            tree[node] += val * (r - l + 1);
            lazy[node] += val;
            return;
        }
        push_down(node, l, r);              // phải đi sâu -> trả nợ trước
        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);              // trả nợ trước khi đọc con
        int mid = (l + r) / 2;
        return query(2 * node,     l,     mid, ql, qr)
             + query(2 * node + 1, mid + 1, r,  ql, qr);
    }
};

Độ phức tạp

Bộ nhớ: $O(N)$ — cụ thể ta cấp tree (và lazy) kích thước $4N$. Lý do hệ số 4: khi $N$ không phải lũy thừa của 2, đánh số kiểu heap có thể nhảy tới chỉ số lớn gần $4N$ ở tầng lá sâu nhất. Cấp $4N$ luôn đủ chỗ; cấp $2N$ có thể truy cập ngoài mảng.

⚠️ Lỗi thường gặp

• Tràn số (overflow): tổng của $N\approx {10}^5$ phần tử cỡ ${10}^9$ vượt xa int ($\approx 2.1\times {10}^9$). Dùng long long cho mảng tree. Với lazy, biểu thức lazy * (r - l + 1) còn dễ tràn hơn — cả lazy lẫn kết quả phải là long long.
• Cấp phát thiếu bộ nhớ: dùng 2*n thay vì 4*n cho tree gây truy cập ngoài mảng (UB, có thể RE/WA ngẫu nhiên với $N$ không là lũy thừa 2). Luôn cấp 4*n.
• Quên push_down trong lazy: đọc/ghi node con khi node cha còn "nợ" chưa đẩy xuống → kết quả sai. Phải gọi push_down trước khi đệ quy xuống con ở cả update lẫn query.
• Sai phần tử trung tính khi đổi phép gộp: với min phải trả LLONG_MAX (không phải 0) cho nhánh không giao; trả 0 sẽ làm min luôn bằng 0. Với max trả LLONG_MIN, với gcd trả 0.
• Nhầm phép gộp trong lazy không tương thích: lazy cho "cộng đoạn + truy vấn tổng" khác hẳn lazy cho "gán đoạn" hay "cộng đoạn + truy vấn min". Khi đổi loại cập nhật phải sửa cả công thức cập nhật tree[node] lẫn cách dồn nợ trong push_down; sao chép máy móc dễ sai.
• Off-by-one ở biên đoạn: trộn lẫn 0-based và 1-based giữa input và cây, hoặc gọi query với [l, r] mà input là [l, r). Cố định một quy ước (ở đây: 0-based, đoạn toàn cục [0, n-1]) và dùng nhất quán.

Biến thể / Mở rộng

• So với Fenwick Tree (BIT): Fenwick gọn và nhanh hơn hằng số cho tổng/đếm tiền tố, nhưng Segment Tree linh hoạt hơn: làm được min/max (Fenwick rất khó), lazy propagation logic phức tạp (gán đoạn, kết hợp nhiều loại cập nhật), và lưu nhiều thông tin trên mỗi node. Xem thêm Fenwick Tree.
• Tìm kiếm trên cây (descend): đi từ gốc xuống để trả lời "vị trí trái nhất có $\ge k$ chỗ trống liên tiếp" hoặc "phần tử thứ $k$" trong $O(\log N)$, thay vì binary search bọc ngoài thành $O({\log }^{2}N)$.
• Segment Tree động / nén toạ độ: khi miền chỉ số rất lớn (${10}^9$) nhưng số điểm ít, nén toạ độ hoặc tạo node theo nhu cầu (dynamic / sparse segment tree).
• Persistent Segment Tree: giữ lại mọi phiên bản sau cập nhật, trả lời truy vấn trên trạng thái quá khứ.

Bài tập luyện

• Đếm Kiện Cỏ (haybales15) — (Advanced) lazy propagation kinh điển: cộng cả đoạn, truy vấn min và tổng đoạn — bài nhập môn để luyện push_down.
• Marathon (marathong) — (Veteran) cập nhật điểm + truy vấn đoạn với phép gộp tuỳ biến (giữ tổng khoảng cách và mức tiết kiệm lớn nhất khi bỏ một điểm).
• Sắp Xếp Chỗ Ngồi (seating) — (Veteran) mỗi node lưu độ dài đoạn trống dài nhất (kèm tiền tố/hậu tố) rồi đi xuống cây tìm vị trí trái nhất đủ chỗ.
• Phá Mã (codebreak) — (Veteran) kết hợp Segment Tree với quy hoạch động trên cây — bài tổng hợp nâng cao.