Persistent Segment Tree

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

huunguyen · Last updated 8, Tháng 4, 2026, 16:03

Persistent Segment Tree (cây phân đoạn bền vững) lưu nhiều phiên bản của segment tree sau mỗi cập nhật, mỗi phiên bản chỉ tốn $O (\log N)$ node mới (chia sẻ phần còn lại với phiên bản cũ).

Ứng dụng: Truy vấn đoạn tại thời điểm $t$ bất kỳ, tìm phần tử thứ $k$ trong đoạn $[l, r]$ , Merge Sort Tree thay thế.

Ý tưởng

Khi cập nhật điểm $i$ , chỉ $O (\log N)$ node trên đường từ gốc đến lá thay đổi. Thay vì sửa in-place, tạo node mới cho mỗi node thay đổi và giữ nguyên các node còn lại. Mỗi phiên bản có một gốc riêng.

Cài đặt

const int MAXNODES = 20000000;   // đủ cho N*logN node

struct Node {
    int left, right;
    long long sum;
} tree[MAXNODES];
int node_cnt = 0;

int new_node() { return ++node_cnt; }

// Build phiên bản 0 (cây rỗng hoặc từ mảng a)
int build(int l, int r) {
    int cur = new_node();
    tree[cur] = {0, 0, 0};
    if (l == r) return cur;
    int mid = (l + r) / 2;
    tree[cur].left  = build(l, mid);
    tree[cur].right = build(mid+1, r);
    return cur;
}

// Cập nhật điểm pos, trả về root mới
int update(int prev, int l, int r, int pos, long long val) {
    int cur = new_node();
    tree[cur] = tree[prev];   // copy node cũ
    if (l == r) {
        tree[cur].sum += val;
        return cur;
    }
    int mid = (l + r) / 2;
    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);
    tree[cur].sum = tree[tree[cur].left].sum + tree[tree[cur].right].sum;
    return cur;
}

// Truy vấn tổng [ql,qr] trên phiên bản root
long long 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) / 2;
    return query(tree[root].left, l, mid, ql, qr)
         + query(tree[root].right, mid+1, r, ql, qr);
}

Ví dụ: Truy vấn tại thời điểm $t$

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

int main() {
    int n, q; cin >> n >> q;
    roots.push_back(build(1, n));   // phiên bản 0: cây rỗng

    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int pos, val; cin >> pos >> val;
            roots.push_back(update(roots.back(), 1, n, pos, val));
        } else {
            int t, l, r; cin >> t >> l >> r;
            cout << query(roots[t], 1, n, l, r) << "\n";
        }
    }
}

Ứng dụng: Phần tử thứ $k$ trong đoạn $[l, r]$

Dùng Persistent Segment Tree trên tọa độ nén: phiên bản $i$ = cây sau khi thêm $a [1 . . i]$ .

// Phần tử thứ k nhỏ nhất trong a[l..r]
// roots[i] = PST sau khi insert a[i] vào cây tọa độ
int kth(int lo, int hi, int l, int r, int k) {
    // lo, hi: root của phiên bản l-1 và r
    if (l == r) return l;   // l là tọa độ (sau nén)
    int mid = (l + r) / 2;
    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: kth(roots[l-1], roots[r], 1, max_val, k)
// Trả về tọa độ nén → map ngược ra giá trị thực

Độ phức tạp

	Build	Update	Query
Persistent Segment Tree	$O (N)$	$O (\log N)$ (node mới)	$O (\log N)$
Bộ nhớ	$O (N)$ ban đầu + $O (Q \log N)$ tổng

Khi nào dùng Persistent Segment Tree?

Truy vấn đoạn tại phiên bản lịch sử bất kỳ.
Tìm phần tử thứ $k$ trong đoạn $[l, r]$ (Merge Sort Tree thay thế).
Khi cần "undo" cập nhật hoặc so sánh hai phiên bản.

Bình luận

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