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

Persistent Segment Tree

huunguyen Updated Tháng sáu 2, 2026

Persistent Segment Tree (cây phân đoạn bền vững) là biến thể của segment tree cho phép lưu mọi phiên bản của cây sau từng cập nhật, mà không sao chép lại toàn bộ cây. Mỗi cập nhật điểm chỉ tạo thêm $O (\log N)$ node mới và dùng chung (share) toàn bộ phần không đổi với phiên bản trước. Nhờ vậy ta có thể truy vấn cây ở bất kỳ thời điểm lịch sử nào trong $O (\log N)$ , và tổng bộ nhớ chỉ là $O (N + Q \log N)$ thay vì $O (N \cdot Q)$ như khi sao chép thô.

Ứng dụng kinh điển:

Truy vấn đoạn trên phiên bản $t$ bất kỳ (rollback / so sánh hai mốc thời gian).
Tìm phần tử lớn/nhỏ thứ $k$ trong đoạn $[l, r]$ (range $k$ -th) — thay thế Merge Sort Tree với truy vấn $O (\log N)$ .
Đếm số phần tử $\leq x$ trong $[l, r]$ , đếm số giá trị phân biệt, v.v.

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

Hãy nhìn lại một cập nhật điểm trên segment tree thường: khi sửa giá trị tại vị trí $p o s$ , chỉ những node nằm trên đường đi từ gốc xuống lá $p o s$ bị ảnh hưởng — đúng $O (\log N)$ node. Tất cả các node khác giữ nguyên giá trị.

Đây là chìa khóa của tính bền vững (persistence): thay vì ghi đè các node trên đường đi đó, ta tạo bản sao mới cho từng node trên đường đi, còn các nhánh con không đổi thì cho con trỏ trỏ thẳng vào node của phiên bản cũ. Kết quả:

Phiên bản mới có một gốc mới riêng.
Đi từ gốc mới xuống, ta gặp $O (\log N)$ node "mới tinh", và tại nhánh nào không thay đổi thì lập tức "nhảy" sang dùng lại cây con cũ.
Phiên bản cũ vẫn nguyên vẹn vì ta chưa hề chạm vào node nào của nó.

Vì sao điều này đúng? Vì segment tree là cấu trúc bất biến cục bộ: giá trị một node chỉ phụ thuộc hai con. Nếu hai con của một node không đổi thì node đó cũng không đổi, nên việc chia sẻ cây con là hoàn toàn hợp lệ. Mỗi node là bất biến (immutable) sau khi tạo — không bao giờ bị sửa — nên nhiều phiên bản trỏ chung vào nó mà không xung đột.

Với bài range $k$ -th nhỏ nhất, ta khai thác thêm một mẹo cộng dồn: dựng PST trên trục giá trị (đã nén tọa độ), trong đó phiên bản $i$ là cây đếm tần suất sau khi chèn $a [1], a [2], \dots, a [i]$ . Khi đó "số phần tử trong đoạn giá trị $[l o, h i]$ thuộc về mảng con $a [l . . r]$ " chính là count(phiên bản r) - count(phiên bản l-1). Phép trừ này hoạt động vì hai phiên bản cùng hình dạng cây và cùng hệ tọa độ, nên ta có thể đi song song hai cây và lấy hiệu số đếm ở từng node — đó là prefix-sum trên cây.

Ví dụ chạy tay

Xét $N = 4$ , lần lượt cập nhật (cộng 1) tại các vị trí: thời điểm 1 thêm tại $p o s = 2$ , thời điểm 2 thêm tại $p o s = 4$ . Cây trên đoạn chỉ số $[1, 4]$ , mỗi node ghi tổng.

Phiên bản 0 (cây rỗng) — gốc $R_{0}$ :

                 [1..4] sum=0
                /            \
          [1..2] s=0      [3..4] s=0
          /     \          /     \
     [1] s=0 [2] s=0  [3] s=0 [4] s=0

Cập nhật $p o s = 2$ tạo phiên bản 1. Đường đi gốc → lá 2 là: [1..4] -> [1..2] -> [2]. Chỉ 3 node này được nhân bản (đánh dấu *); nhánh [3..4] được chia sẻ lại từ $R_{0}$ :

   R1: [1..4]* s=1
        /         \
  [1..2]* s=1     (trỏ về [3..4] s=0 CỦA R0)  <-- share
   /      \
 [1] s=0  [2]* s=1     <-- chỉ 3 node mới: ^ ^ ^

Tổng số node mới tạo cho phiên bản 1 = 3 = chiều cao cây = $O (\log N)$ .

Cập nhật $p o s = 4$ trên $R_{1}$ tạo phiên bản 2. Đường đi: [1..4] -> [3..4] -> [4]. Lần này nhánh trái [1..2] (cùng giá trị $R_{1}$ ) được chia sẻ lại từ $R_{1}$ :

   R2: [1..4]* s=2
        /          \
  (share [1..2] s=1 CỦA R1)   [3..4]* s=1
                               /      \
                          [3] s=0   [4]* s=1

Bây giờ ta có 3 gốc cùng tồn tại. Truy vấn tổng $[1, 4]$ :

Trên $R_{0}$ : $0$ .
Trên $R_{1}$ : $1$ (mới có $p o s = 2$ ).
Trên $R_{2}$ : $2$ .

Quan sát quan trọng: tổng node thực sự được tạo = (build $R_{0}$ : 7 node) + (mỗi update: 3 node). Phần lớn cây được dùng lại, không nhân đôi. Đó là lý do bộ nhớ chỉ $O (N + Q \log N)$ .

Sơ đồ chia sẻ con trỏ (mũi tên = "trỏ tới"):

R0 ─┬─ [3..4]s0 ◄──────────── R1.right (share)
    └─ ...
R1 ─┬─ [1..2]s1 ◄──────────── R2.left  (share)
    └─ ...
R2 ─── nodes mới cho nhánh phải

Cài đặt

Mỗi node lưu chỉ số con trái/phải (không phải con trỏ thật) vào một mảng node tĩnh — cấp phát nhanh và tránh rò rỉ bộ nhớ.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXNODES = 20000000;   // ~ 4*N + Q*ceil(log2 N) + dự phòng

struct Node {
    int left, right;   // CHỈ SỐ của hai con trong mảng tree[]
    ll sum;
} tree[MAXNODES];
int node_cnt = 0;

int new_node() { return ++node_cnt; }   // node 0 dùng làm "null" sum=0

// Dựng phiên bản 0 (cây rỗng) trên đoạn chỉ số [l, r]
int build(int l, int r) {
    int cur = new_node();
    tree[cur] = {0, 0, 0};
    if (l == r) return cur;
    int mid = (l + r) >> 1;
    tree[cur].left  = build(l, mid);
    tree[cur].right = build(mid + 1, r);
    return cur;
}

// Cập nhật điểm pos (+val) trên phiên bản 'prev', trả về GỐC MỚI.
// Quan trọng: KHÔNG sửa node cũ; chỉ tạo bản sao trên đường đi.
int update(int prev, int l, int r, int pos, ll val) {
    int cur = new_node();
    tree[cur] = tree[prev];          // sao chép node cũ (gồm cả 2 con share)
    if (l == r) {
        tree[cur].sum += val;        // tới lá: cập nhật giá trị
        return cur;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        tree[cur].left  = update(tree[prev].left,  l, mid, pos, val);
    else
        tree[cur].right = update(tree[prev].right, mid + 1, r, pos, val);
    // gộp lại từ hai con (một con mới, một con vẫn là của 'prev')
    tree[cur].sum = tree[tree[cur].left].sum + tree[tree[cur].right].sum;
    return cur;
}

// Truy vấn tổng [ql, qr] trên một phiên bản gốc 'root'
ll query(int root, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return tree[root].sum;
    int mid = (l + r) >> 1;
    return query(tree[root].left,  l, mid,     ql, qr)
         + query(tree[root].right, mid + 1, r, ql, qr);
}

Lưu danh sách gốc để truy cập từng phiên bản:

vector<int> roots;   // roots[t] = gốc sau cập nhật thứ t

int main(){
    int n, q; scanf("%d %d", &n, &q);
    roots.push_back(build(1, n));        // phiên bản 0
    while (q--) {
        int type; scanf("%d", &type);
        if (type == 1) {                 // cập nhật, sinh phiên bản mới
            int pos; ll val; scanf("%d %lld", &pos, &val);
            roots.push_back(update(roots.back(), 1, n, pos, val));
        } else {                         // hỏi trên phiên bản t
            int t, l, r; scanf("%d %d %d", &t, &l, &r);
            printf("%lld\n", query(roots[t], 1, n, l, r));
        }
    }
}

Ứng dụng: phần tử thứ $k$ nhỏ nhất trong $[l, r]$

Nén tọa độ giá trị, dựng PST trên trục giá trị: roots[i] = cây đếm tần suất sau khi chèn $a [1 . . i]$ . Đi song song hai phiên bản và lấy hiệu prefix:

// 'lo' = gốc phiên bản (l-1), 'hi' = gốc phiên bản r; [l,r] ở đây là đoạn GIÁ TRỊ
int kth(int lo, int hi, int l, int r, int k) {
    if (l == r) return l;                // l là tọa độ nén của đáp án
    int mid = (l + r) >> 1;
    // số phần tử của a[L..R] rơi vào nửa giá trị trái = hiệu hai cây
    int left_cnt = tree[tree[hi].left].sum - tree[tree[lo].left].sum;
    if (k <= left_cnt)
        return kth(tree[lo].left,  tree[hi].left,  l, mid, k);
    else
        return kth(tree[lo].right, tree[hi].right, mid + 1, r, k - left_cnt);
}
// Gọi: int code = kth(roots[L-1], roots[R], 1, M, k);  // M = số giá trị phân biệt
//       giá trị thực = giải nén tọa độ ở code

Độ phức tạp

Thao tác	Thời gian	Lý giải
Build phiên bản 0	$O (N)$	duyệt toàn bộ $2 N - 1$ node một lần
Update (sinh phiên bản)	$O (\log N)$	chỉ nhân bản các node trên một đường gốc→lá, dài đúng $⌈ \log_{2} N ⌉$
Query đoạn	$O (\log N)$	phân rã đoạn thành $O (\log N)$ node phủ
$k$ -th trong $[l, r]$	$O (\log N)$	đi xuống một đường duy nhất, mỗi bước trừ hai con trong $O (1)$

Bộ nhớ: $O (N + Q \log N)$ . Build tốn $\approx 2 N$ node; mỗi cập nhật thêm đúng $⌈ \log_{2} N ⌉$ node mới (do chia sẻ phần còn lại). Với $Q$ cập nhật, tổng số node $\approx 2 N + Q ⌈ \log_{2} N ⌉$ . Đây chính là điểm mạnh: nếu sao chép cả cây mỗi lần thì sẽ là $O (N Q)$ — không khả thi.

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

Cấp phát mảng node thiếu chỗ. MAXNODES phải $\geq 2 N + Q ⌈ \log_{2} N ⌉$ cộng dự phòng. Tính nhầm (ví dụ chỉ để $4 N$ ) gây ghi đè ngoài mảng → kết quả sai ngẫu nhiên hoặc RE. Luôn ước lượng dư, ví dụ $N \log N + 2 N$ và làm tròn lên.
Sửa node cũ (phá tính bền vững). Trong update, sau tree[cur] = tree[prev]; mọi thay đổi phải áp lên cur, không bao giờ lên prev hay con của prev. Một dòng vô tình ghi tree[prev].sum = ... sẽ làm hỏng tất cả phiên bản đang chia sẻ node đó — bug rất khó truy.
Tràn số (overflow). sum phải là long long nếu tổng có thể vượt $2^{31}$ (ví dụ $N = 10^{5}$ , mỗi giá trị $10^{9}$ ). Để int sẽ tràn âm thầm. Riêng cây đếm tần suất cho bài $k$ -th thì int đủ, nhưng đừng nhầm hai loại cây.
Sai biên trong $k$ -th: dùng roots[L-1] chứ không phải roots[L]. Đoạn $[L, R]$ ứng với hiệu phiên bản $R$ và $L - 1$ . Dùng roots[L] sẽ bỏ sót đúng phần tử $a [L]$ → đáp án lệch. Khi $L = 1$ thì roots[0] phải là cây rỗng hợp lệ (đừng quên build phiên bản 0).
Quên nén tọa độ hoặc nén sai. PST trên trục giá trị cần giá trị nằm trong $[1, M]$ liên tục; nếu không nén, cây sâu $\log (maxVal)$ tốn bộ nhớ khổng lồ, hoặc chỉ số âm gây RE. Sau khi tìm được tọa độ nén phải giải nén trả về giá trị thật.
Truyền nhầm phiên bản gốc. Lưu roots theo đúng thứ tự thời gian; truy vấn "tại thời điểm $t$ " phải dùng roots[t], không phải roots.back(). Nhầm chỉ số phiên bản là lỗi logic phổ biến nhất khi mới học.

Biến thể / Mở rộng

PST có lazy propagation (cập nhật đoạn bền vững): mỗi node lazy cũng phải bất biến → "đẩy lazy" bằng cách tạo node mới, tốn $O (\log N)$ node mỗi cập nhật đoạn. Cẩn thận tránh đẩy lazy vào node chia sẻ.
Persistent trên các CTDL khác (persistent DSU, persistent trie) dùng cùng nguyên lý "path-copying" bất biến.
Liên hệ: nếu chỉ cần truy vấn offline range $k$ -th, có thể thay bằng Merge Sort Tree hay Wavelet Tree; PST thắng khi cần online và truy vấn lịch sử. Xem thêm Segment Tree cơ bản tại https://oj.chuyentin.pro/wiki/segment-tree/ và Fenwick Tree tại https://oj.chuyentin.pro/wiki/fenwick-tree/.

Bài tập luyện

Lưu ý: pool CTOJ hiện chưa có bài gắn nhãn persistent chuyên biệt. Các bài dưới đây là bài segment tree (kỹ năng nền tảng bắt buộc trước khi học PST) và một số bài có thể giải bằng PST như cách tiếp cận online; hãy nắm vững segment tree điểm/đoạn trước, rồi luyện chuyển sang tư duy "nhiều phiên bản".

Marathon (Gold) (marathong) — (Veteran) Cập nhật điểm + truy vấn đoạn (tổng quãng đường, bỏ bớt một điểm) trên segment tree; luyện thao tác point-update/range-query là bộ khung của mỗi phiên bản PST.
Sắp Xếp Chỗ Ngồi (seating) — (Veteran) Tìm đoạn trống dài nhất bằng segment tree gộp (prefix/suffix/best), rèn kỹ năng thiết kế thông tin node — nền tảng để mở rộng sang node bền vững.
Máy Phóng (slingshot) — (Expert) Truy vấn min với nén tọa độ trên trục số; chính nén tọa độ + segment tree trên trục giá trị là kỹ thuật dùng lại nguyên vẹn trong bài range $k$ -th của PST.
Tô Màu Cây (snowcow) — (Expert) Xử lý truy vấn theo nhiều mốc/thời điểm với segment tree (offline); luyện tư duy "trạng thái theo thời gian" — đúng tinh thần các phiên bản lịch sử của PST.