Persistent Segment Tree

Sao chép đường đi

Lưu nút bằng ba mảng lc, rc, val và một bộ đếm tot; nút 0 là cây rỗng (con của nó trỏ về chính nó, giá trị 0). Cập nhật tại vị trí $p$ trên phiên bản gốc old:

1. Tạo nút mới, chép con và giá trị từ old.
2. Nếu là lá, sửa giá trị; nếu không, chỉ đệ quy vào con chứa $p$ và trỏ con đó sang nút mới vừa tạo.

Mỗi lần cập nhật tạo đúng (độ sâu cây + 1) nút, khoảng $\lceil \log_2 n \rceil + 1$. Tổng bộ nhớ $O(n + m \log n)$; khai báo mảng nút theo con số này, ví dụ $2n + 21m$ khi $n \le 10^6$. Không bao giờ sửa một nút đã tạo, nên mọi phiên bản cũ vẫn đúng nguyên vẹn.

Trong hình, mỗi màu là các nút tạo ở một phiên bản. Chọn phiên bản để xem cây của nó và xem phần nào được dùng chung.

Ví dụDòng Thời Gian Của Mảng

Đề. Mảng $n \le 10^6$ là phiên bản 0. Thao tác thứ $i$ ($m \le 10^6$) tạo phiên bản $i$ từ một phiên bản cũ $v$: hoặc đổi vị trí $p$ thành $x$, hoặc giữ nguyên và in phần tử ở vị trí $p$.

Lời giải. Cây phân đoạn bền vững trên vị trí. Phiên bản 0 dựng đầy đủ một lần. Đổi vị trí $p$ ở phiên bản $v$ chỉ chép lại các nút trên đường từ gốc tới lá $p$, khoảng 21 nút; mọi nhánh khác dùng chung với phiên bản cũ.

Bước 1: nút đánh số tự do. Nút cấp bằng ++tot; lc, rc là chỉ số nút con, val chỉ có nghĩa ở lá. Kích thước M đủ cho $2n$ nút của phiên bản đầu cộng $m$ lần chép, mỗi lần khoảng $\log_2 10^6 + 1 = 21$ nút. build dựng phiên bản 0 như cây phân đoạn thường, nhưng trả về chỉ số nút thay vì dùng $2x$, $2x + 1$.

Bước 2: cập nhật tạo nút mới. Nút x sao chép old, rồi chỉ thay con nằm phía có $p$ bằng kết quả đệ quy. Con còn lại vẫn trỏ vào nút của phiên bản cũ. Phiên bản cũ không bị đụng tới, nên vẫn đọc đúng như trước.

int update(int old, int l, int r, int p, int v) {
    int x = ++tot;
    lc[x] = lc[old], rc[x] = rc[old], val[x] = val[old];
    if (l == r) {
        val[x] = v;
        return x;
    }
    int mid = (l + r) / 2;
    if (p <= mid) lc[x] = update(lc[old], l, mid, p, v);
    else rc[x] = update(rc[old], mid + 1, r, p, v);
    return x;
}

Bước 3: đọc cũng tạo phiên bản. Thao tác đọc tạo phiên bản giống hệt phiên bản $v$, nên chỉ gán root[i] = root[v], không tạo nút nào. Vẫn phải gán vì thao tác sau có thể dựa trên phiên bản $i$.

if (type == 1) {
    int x;
    cin >> x;
    root[i] = update(root[v], 1, n, p, x);
} else {
    cout << get(root[v], 1, n, p) << '\n';
    root[i] = root[v];
}

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

const int N = 1e6 + 5, M = 2 * N + 21 * N;
int n, m, tot, a[N], root[N], lc[M], rc[M], val[M];

int build(int l, int r) {
    int x = ++tot;
    if (l == r) {
        val[x] = a[l];
        return x;
    }
    int mid = (l + r) / 2;
    lc[x] = build(l, mid);
    rc[x] = build(mid + 1, r);
    return x;
}

int update(int old, int l, int r, int p, int v) {
    int x = ++tot;
    lc[x] = lc[old], rc[x] = rc[old], val[x] = val[old];
    if (l == r) {
        val[x] = v;
        return x;
    }
    int mid = (l + r) / 2;
    if (p <= mid) lc[x] = update(lc[old], l, mid, p, v);
    else rc[x] = update(rc[old], mid + 1, r, p, v);
    return x;
}

int get(int x, int l, int r, int p) {
    while (l < r) {
        int mid = (l + r) / 2;
        if (p <= mid) x = lc[x], r = mid;
        else x = rc[x], l = mid + 1;
    }
    return val[x];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    root[0] = build(1, n);
    for (int i = 1; i <= m; i++) {
        int v, type, p;
        cin >> v >> type >> p;
        if (type == 1) {
            int x;
            cin >> x;
            root[i] = update(root[v], 1, n, p, x);
        } else {
            cout << get(root[v], 1, n, p) << '\n';
            root[i] = root[v];
        }
    }
}

ChạyInput4 6
5 8 2 9
0 2 2
0 1 3 7
2 2 3
1 1 2 -4
4 2 2
2 2 2

Output8
7
-4
8

Mỗi thao tác $O(\log n)$ thời gian và bộ nhớ.

Phần tử thứ k

Nén giá trị về $0..m-1$. Phiên bản $i$ là cây đếm trên miền giá trị, chứa $a_1, \dots, a_i$: root[i] là root[i-1] thêm 1 tại hạng của $a_i$. Số phần tử của đoạn $[l, r]$ có hạng trong một nút là cnt của nút đó ở phiên bản $r$ trừ ở phiên bản $l - 1$, vì hai phiên bản có cùng hình dạng.

Tìm phần tử nhỏ thứ $k$: đi xuống đồng thời trên hai phiên bản. Ở mỗi nút, $c$ là hiệu số đếm của hai con trái; $k \le c$ thì sang trái, ngược lại trừ $k$ đi $c$ rồi sang phải. Mỗi truy vấn $O(\log n)$, trả lời trực tuyến được, khác với cách chặt nhị phân tổng thể.

Ví dụThứ Hạng Trong Đoạn

Đề. Mảng tĩnh $n \le 2 \cdot 10^5$ phần tử, $m \le 2 \cdot 10^5$ truy vấn: phần tử nhỏ thứ $k$ của đoạn $[l, r]$.

Lời giải. Nén giá trị về hạng $0..m-1$. Phiên bản $i$ là cây đếm trên miền hạng, chứa $a_1, \dots, a_i$, dựng bằng cách thêm 1 vào phiên bản $i - 1$ tại hạng của $a_i$. Mọi phiên bản có cùng hình dạng, nên số phần tử của đoạn $[l, r]$ rơi vào một nút là hiệu cnt của nút đó ở phiên bản $r$ và phiên bản $l - 1$.

Bước 1: cây rỗng dùng chung. Nút 0 có cnt[0] = 0 và lc[0] = rc[0] = 0, nên đi xuống từ nút 0 mãi vẫn ở nút 0 với số đếm 0. Nhờ vậy root[0] = 0 không cần dựng.

Bước 2: thêm một phần tử. Chép đường từ gốc tới lá $p$, mỗi nút trên đường tăng cnt thêm 1.

int insert(int old, int l, int r, int p) {
    int x = ++tot;
    lc[x] = lc[old], rc[x] = rc[old], cnt[x] = cnt[old] + 1;
    if (l == r) return x;
    int mid = (l + r) / 2;
    if (p <= mid) lc[x] = insert(lc[old], l, mid, p);
    else rc[x] = insert(rc[old], mid + 1, r, p);
    return x;
}

Bước 3: đi xuống trên hai phiên bản. u là phiên bản $l - 1$, v là phiên bản $r$; c là số phần tử của đoạn có hạng ở nửa trái. $k \le c$ thì phần tử cần tìm ở nửa trái; ngược lại nó là phần tử thứ $k - c$ của nửa phải. Tới lá thì l là hạng cần tìm, vals[...] đổi về giá trị thật.

int kth(int u, int v, int l, int r, int k) {
    while (l < r) {
        int mid = (l + r) / 2, c = cnt[lc[v]] - cnt[lc[u]];
        if (k <= c) u = lc[u], v = lc[v], r = mid;
        else k -= c, u = rc[u], v = rc[v], l = mid + 1;
    }
    return l;
}

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

const int N = 2e5 + 5, M = 20 * N;
int n, q, m, tot, a[N], root[N], lc[M], rc[M], cnt[M];
vector<int> vals;

int insert(int old, int l, int r, int p) {
    int x = ++tot;
    lc[x] = lc[old], rc[x] = rc[old], cnt[x] = cnt[old] + 1;
    if (l == r) return x;
    int mid = (l + r) / 2;
    if (p <= mid) lc[x] = insert(lc[old], l, mid, p);
    else rc[x] = insert(rc[old], mid + 1, r, p);
    return x;
}

int kth(int u, int v, int l, int r, int k) {
    while (l < r) {
        int mid = (l + r) / 2, c = cnt[lc[v]] - cnt[lc[u]];
        if (k <= c) u = lc[u], v = lc[v], r = mid;
        else k -= c, u = rc[u], v = rc[v], l = mid + 1;
    }
    return l;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i], vals.push_back(a[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    m = vals.size();
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
        root[i] = insert(root[i - 1], 0, m - 1, p);
    }
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << vals[kth(root[l - 1], root[r], 0, m - 1, k)] << '\n';
    }
}

ChạyInput7 4
4 0 4 7 2 0 5
1 7 3
2 5 2
3 6 4
4 4 1

Output2
2
7
7

Mỗi truy vấn $O(\log n)$, không cần đọc trước các truy vấn khác. Cây này nhảy khắp bộ nhớ, nên cách bố trí nút ảnh hưởng thấy rõ:

Gộp lc, rc, cnt vào một struct nhanh hơn ba mảng riêng khoảng 1,3 lần, vì một lần đọc nút kéo luôn cả ba trường vào bộ nhớ đệm. Quy tắc: các trường luôn đọc cùng nhau thì đặt cạnh nhau.

Đếm theo ngưỡng

Cùng các phiên bản tiền tố trả lời được “có bao nhiêu phần tử của $[l, r]$ có giá trị trong khoảng $[x, y]$”: lấy tổng cnt của khoảng hạng tương ứng ở phiên bản $r$ trừ ở phiên bản $l - 1$.

Khi không bắt buộc trực tuyến, bài này còn giải được bằng Fenwick và sắp truy vấn theo ngưỡng. Phiên bản bền vững hữu ích khi đề mã hóa truy vấn bằng đáp án trước, hoặc khi số chiều điều kiện nhiều hơn.

Thay cnt bằng tổng giá trị thì được “tổng các phần tử không vượt $X$ trong đoạn”; đổi điểm cập nhật thì đếm được số giá trị phân biệt (chỉ giữ lần xuất hiện cuối).

Ví dụVượt Qua Ngưỡng

Đề. Mảng $n \le 3 \cdot 10^4$, $q \le 2 \cdot 10^5$ truy vấn: đếm $i \in [l, r]$ có $a_i > k$.

Lời giải. Cùng các phiên bản tiền tố như ví dụ trước (insert giống hệt). Phần tử lớn hơn $k$ là những phần tử có hạng từ upper_bound(k) trở đi; số phần tử như vậy trong đoạn $[l, r]$ là tổng đếm của khoảng hạng đó ở phiên bản $r$ trừ ở phiên bản $l - 1$.

Bước 1: đếm hạng $\ge ql$. Nút nằm hẳn bên trái $ql$, hoặc không có phần tử nào của đoạn, thì trả 0. Nút nằm hẳn bên phải $ql$ thì trả cả hiệu đếm. Còn lại tách làm hai nửa.

int countFrom(int u, int v, int l, int r, int ql) {
    if (r < ql || cnt[v] - cnt[u] == 0) return 0;
    if (ql <= l) return cnt[v] - cnt[u];
    int mid = (l + r) / 2;
    return countFrom(lc[u], lc[v], l, mid, ql) + countFrom(rc[u], rc[v], mid + 1, r, ql);
}

Bước 2: truy vấn. Nếu $k$ lớn hơn mọi giá trị thì p = m, mọi nút đều có r < ql và kết quả là 0.

int p = upper_bound(vals.begin(), vals.end(), k) - vals.begin();
cout << countFrom(root[l - 1], root[r], 0, m - 1, p) << '\n';

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

const int N = 3e4 + 5, M = 20 * N;
int n, q, m, tot, a[N], root[N], lc[M], rc[M], cnt[M];
vector<int> vals;

int insert(int old, int l, int r, int p) {
    int x = ++tot;
    lc[x] = lc[old], rc[x] = rc[old], cnt[x] = cnt[old] + 1;
    if (l == r) return x;
    int mid = (l + r) / 2;
    if (p <= mid) lc[x] = insert(lc[old], l, mid, p);
    else rc[x] = insert(rc[old], mid + 1, r, p);
    return x;
}

int countFrom(int u, int v, int l, int r, int ql) {
    if (r < ql || cnt[v] - cnt[u] == 0) return 0;
    if (ql <= l) return cnt[v] - cnt[u];
    int mid = (l + r) / 2;
    return countFrom(lc[u], lc[v], l, mid, ql) + countFrom(rc[u], rc[v], mid + 1, r, ql);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], vals.push_back(a[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    m = vals.size();
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
        root[i] = insert(root[i - 1], 0, m - 1, p);
    }
    cin >> q;
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        int p = upper_bound(vals.begin(), vals.end(), k) - vals.begin();
        cout << countFrom(root[l - 1], root[r], 0, m - 1, p) << '\n';
    }
}

ChạyInput6
5 1 9 5 2 8
5
1 6 5
2 5 4
3 6 8
1 3 9
4 4 1

Output2
2
1
0
1

Mỗi truy vấn đi qua $O(\log n)$ nút như truy vấn đoạn của cây phân đoạn thường.

Phiên bản trên cây

Trên cây gốc 1, cho phiên bản của đỉnh $v$ là phiên bản của cha thêm giá trị của $v$: nó chứa đúng các giá trị trên đường từ gốc tới $v$. Đa tập trên đường $u \to v$ với $w = \operatorname{lca}(u, v)$ là

trừ $T_w$ hai lần sẽ mất $w$, nên chỉ trừ một lần và trừ thêm phiên bản của cha nó. Tìm phần tử thứ $k$ bằng cách đi xuống đồng thời trên bốn phiên bản. Dựng phiên bản theo thứ tự BFS để cha luôn có trước con.

Ví dụThứ Hạng Trên Đường Cây

Đề. Cây $n \le 10^5$ đỉnh có trọng số, $m \le 10^5$ truy vấn trực tuyến: đầu mút thật $u = U \oplus last$, tìm trọng số nhỏ thứ $k$ trên đường $u \to v$.

Lời giải. Phiên bản của đỉnh $u$ là phiên bản của cha thêm trọng số của $u$, nên nó chứa đúng các trọng số trên đường từ gốc tới $u$. Đường $u \to v$ với $c = \operatorname{lca}(u, v)$ có đa tập trọng số bằng $T_u + T_v - T_c - T_{\operatorname{par}(c)}$; tìm phần tử thứ $k$ bằng cách đi xuống đồng thời trên bốn phiên bản. Đề mã hóa đầu mút $u$ bằng đáp án trước, nên phải trả lời lần lượt từng truy vấn.

Bước 1: phiên bản theo BFS. Khi lấy $u$ ra khỏi order, cha up[0][u] đã được xử lý trước nên root[up[0][u]] có sẵn. Gốc có cha là 0, tức cây rỗng.

for (int i = 0; i < (int)order.size(); i++) {
    int u = order[i];
    int p = lower_bound(vals.begin(), vals.end(), w[u]) - vals.begin();
    root[u] = insert(root[up[0][u]], 0, m - 1, p);
    for (int v : adj[u])
        if (v != up[0][u]) up[0][v] = u, dep[v] = dep[u] + 1, order.push_back(v);
}

Bước 2: LCA bằng nhảy nhị phân. up[j][v] là tổ tiên thứ $2^j$, dựng sau BFS. Nâng đỉnh sâu hơn lên cùng độ sâu, rồi nâng cả hai từ bước lớn xuống bước nhỏ khi tổ tiên còn khác nhau.

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = LOG - 1; j >= 0; j--)
        if (dep[u] - (1 << j) >= dep[v]) u = up[j][u];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--)
        if (up[j][u] != up[j][v]) u = up[j][u], v = up[j][v];
    return up[0][u];
}

Bước 3: đi xuống trên bốn phiên bản. x là số trọng số trên đường có hạng ở nửa trái, tính bằng $a + b - c - d$ theo đúng công thức đa tập. Khi LCA là gốc, up[0][c] = 0 và root[0] = 0 là cây rỗng, nên công thức vẫn đúng.

int kth(int a, int b, int c, int d, int l, int r, int k) {
    while (l < r) {
        int mid = (l + r) / 2, x = cnt[lc[a]] + cnt[lc[b]] - cnt[lc[c]] - cnt[lc[d]];
        if (k <= x) a = lc[a], b = lc[b], c = lc[c], d = lc[d], r = mid;
        else k -= x, a = rc[a], b = rc[b], c = rc[c], d = rc[d], l = mid + 1;
    }
    return l;
}

last giữ đáp án trước, giải mã u = U ^ last trước khi tính.

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

const int N = 1e5 + 5, M = 20 * N, LOG = 17;
int n, q, m, tot, root[N], dep[N], up[LOG][N], lc[M], rc[M], cnt[M];
ll w[N];
vector<int> adj[N];
vector<ll> vals;

int insert(int old, int l, int r, int p) {
    int x = ++tot;
    lc[x] = lc[old], rc[x] = rc[old], cnt[x] = cnt[old] + 1;
    if (l == r) return x;
    int mid = (l + r) / 2;
    if (p <= mid) lc[x] = insert(lc[old], l, mid, p);
    else rc[x] = insert(rc[old], mid + 1, r, p);
    return x;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = LOG - 1; j >= 0; j--)
        if (dep[u] - (1 << j) >= dep[v]) u = up[j][u];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--)
        if (up[j][u] != up[j][v]) u = up[j][u], v = up[j][v];
    return up[0][u];
}

int kth(int a, int b, int c, int d, int l, int r, int k) {
    while (l < r) {
        int mid = (l + r) / 2, x = cnt[lc[a]] + cnt[lc[b]] - cnt[lc[c]] - cnt[lc[d]];
        if (k <= x) a = lc[a], b = lc[b], c = lc[c], d = lc[d], r = mid;
        else k -= x, a = rc[a], b = rc[b], c = rc[c], d = rc[d], l = mid + 1;
    }
    return l;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> w[i], vals.push_back(w[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    m = vals.size();
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> order = {1};
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        int p = lower_bound(vals.begin(), vals.end(), w[u]) - vals.begin();
        root[u] = insert(root[up[0][u]], 0, m - 1, p);
        for (int v : adj[u])
            if (v != up[0][u]) up[0][v] = u, dep[v] = dep[u] + 1, order.push_back(v);
    }
    for (int j = 1; j < LOG; j++)
        for (int v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    ll last = 0;
    while (q--) {
        ll U;
        int v, k;
        cin >> U >> v >> k;
        int u = U ^ last, c = lca(u, v);
        last = vals[kth(root[u], root[v], root[c], root[up[0][c]], 0, m - 1, k)];
        cout << last << '\n';
    }
}

+11 dòngChạyInput6 4
8 3 10 3 6 12
1 2
1 3
2 4
2 5
3 6
4 6 3
13 4 2
2 5 2
0 6 1

Output8
3
6
12

Mỗi truy vấn $O(\log n)$.