Balanced Binary Search Tree

Treap theo khóa: tách và ghép

Nút $t$ có key, độ ưu tiên ngẫu nhiên pr, hai con lc, rc và kích thước sz. Hai thao tác nền:

• split(t, k, a, b): tách cây $t$ thành $a$ gồm các khóa $\le k$ và $b$ gồm các khóa $> k$. Nếu gốc có khóa $\le k$ thì gốc và cây con trái thuộc $a$, chỉ cần tách tiếp cây con phải; ngược lại đối xứng.
• merge(a, b) với mọi khóa của $a$ nhỏ hơn mọi khóa của $b$: gốc mới là gốc có độ ưu tiên lớn hơn, đệ quy ghép phần còn lại vào con tương ứng.

Cả hai chỉ đi dọc một đường từ gốc, nên tốn đúng chiều cao, kỳ vọng $O(\log n)$. Sau mỗi lần sửa con, cập nhật sz (hàm pull). Từ đó:

• Chèn $x$: tách theo $x$, ghép $a$, nút mới, $b$.
• Xóa một bản $x$: tách ra phần bằng $x$, bỏ gốc của phần đó bằng cách ghép hai con của nó.
• Hạng của $x$: kích thước phần $< x$ cộng 1. Phần tử thứ $k$: đi xuống, so $k$ với kích thước con trái.

Độ ưu tiên lấy từ mt19937; nếu dùng hàm băm cố định, đối thủ có thể dựng test làm cây suy biến.

Ví dụĐa tập có thứ tự

Đề. $n \le 10^5$ thao tác trên một đa tập số nguyên: chèn, xóa một bản, hỏi hạng của $x$, phần tử nhỏ thứ $k$, tiền nhiệm và kế nhiệm nghiêm ngặt.

Lời giải. Mọi thao tác quy về tách theo khóa rồi ghép lại:

• Chèn $x$: tách thành phần $\le x$ và $> x$, ghép nút mới vào giữa.
• Xóa một bản $x$: tách lấy riêng phần bằng $x$, bỏ đúng gốc của phần đó, ghép lại.
• Hạng của $x$: số phần tử $< x$ cộng 1, đọc từ sz sau khi tách tại $x - 1$.
• Phần tử thứ $k$: đi xuống theo sz của con trái, không cần tách.
• Tiền nhiệm là phần tử lớn nhất của phần $< x$; kế nhiệm là phần tử nhỏ nhất của phần $> x$.

Bước 1: tách theo khóa. Gốc có khóa $\le k$ thì gốc cùng cả cây con trái thuộc a, chỉ còn tách tiếp cây con phải; phần $\le k$ của cây con phải trở thành con phải mới của gốc. Ngược lại đối xứng. pull tính lại sz trên đường về.

void split(int t, int k, int &a, int &b) {
    if (!t) {
        a = b = 0;
        return;
    }
    if (key[t] <= k) a = t, split(rc[t], k, rc[t], b), pull(a);
    else b = t, split(lc[t], k, a, lc[t]), pull(b);
}

Bước 2: ghép. Mọi khóa của a nhỏ hơn mọi khóa của b. Gốc nào ưu tiên lớn hơn làm gốc mới, phần còn lại ghép đệ quy vào phía tương ứng. Cây kết quả vẫn là cây tìm kiếm theo khóa và đống theo ưu tiên. Độ ưu tiên lấy từ mt19937 gieo bằng đồng hồ, nên không dựng được test làm cây suy biến.

int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (pr[a] > pr[b]) {
        rc[a] = merge(rc[a], b), pull(a);
        return a;
    }
    lc[b] = merge(a, lc[b]), pull(b);
    return b;
}

Bước 3: xóa một bản. Sau hai lần tách, c chứa mọi bản của $x$. merge(lc[c], rc[c]) bỏ đúng một nút là gốc của c; nếu $x$ không có thì c = 0 và không có gì đổi.

split(root, x, a, b);
split(a, x - 1, a, c);
c = merge(lc[c], rc[c]);
root = merge(merge(a, c), b);

Bước 4: tiền nhiệm, kế nhiệm. kth(a, sz[a]) là phần tử lớn nhất của a, kth(b, 1) là phần tử nhỏ nhất của b. Đề bảo đảm phần đó không rỗng.

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

const int N = 1e5 + 5;
int tot, root, key[N], lc[N], rc[N], sz[N];
unsigned pr[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int newNode(int k) {
    key[++tot] = k, pr[tot] = rng(), sz[tot] = 1;
    return tot;
}

void pull(int t) {
    sz[t] = 1 + sz[lc[t]] + sz[rc[t]];
}

void split(int t, int k, int &a, int &b) {
    if (!t) {
        a = b = 0;
        return;
    }
    if (key[t] <= k) a = t, split(rc[t], k, rc[t], b), pull(a);
    else b = t, split(lc[t], k, a, lc[t]), pull(b);
}

int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (pr[a] > pr[b]) {
        rc[a] = merge(rc[a], b), pull(a);
        return a;
    }
    lc[b] = merge(a, lc[b]), pull(b);
    return b;
}

int kth(int t, int k) {
    while (true) {
        if (k <= sz[lc[t]]) t = lc[t];
        else if (k == sz[lc[t]] + 1) return key[t];
        else k -= sz[lc[t]] + 1, t = rc[t];
    }
}

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

    int n;
    cin >> n;
    while (n--) {
        int op, x, a, b, c;
        cin >> op >> x;
        if (op == 1) {
            split(root, x, a, b);
            root = merge(merge(a, newNode(x)), b);
        } else if (op == 2) {
            split(root, x, a, b);
            split(a, x - 1, a, c);
            c = merge(lc[c], rc[c]);
            root = merge(merge(a, c), b);
        } else if (op == 3) {
            split(root, x - 1, a, b);
            cout << sz[a] + 1 << '\n';
            root = merge(a, b);
        } else if (op == 4) cout << kth(root, x) << '\n';
        else if (op == 5) {
            split(root, x - 1, a, b);
            cout << kth(a, sz[a]) << '\n';
            root = merge(a, b);
        } else {
            split(root, x, a, b);
            cout << kth(b, 1) << '\n';
            root = merge(a, b);
        }
    }
}

+13 dòngInput12
1 4
1 1
1 4
3 4
4 3
5 4
6 1
2 4
3 4
4 2
2 1
4 1

Output2
4
1
4
2
4
4

Chiều cao kỳ vọng $O(\log n)$, nên mỗi thao tác $O(\log n)$ kỳ vọng.

Treap ẩn khóa: thao tác theo vị trí

Bỏ khóa, coi thứ tự giữa các nút chính là thứ tự trong dãy: vị trí của một nút là số nút đứng trước nó, tính được từ sz. Tách theo kích thước split(t, k, a, b) cho $a$ là $k$ phần tử đầu: nếu con trái có ít hơn $k$ nút thì gốc thuộc $a$, tách tiếp con phải với $k - sz_{lc} - 1$.

Khi đó dãy hỗ trợ: tách đoạn $[l, r]$ bằng hai lần tách (lấy $l - 1$ phần tử đầu, rồi $r - l + 1$ phần tử tiếp), xử lý đoạn giữa, ghép lại theo thứ tự tùy ý. Cắt đoạn rồi dán xuống cuối chỉ là ghép lại theo thứ tự trái, phải, giữa. Dựng cây ban đầu bằng cách ghép từng phần tử vào cuối, $O(n \log n)$; in dãy bằng duyệt trung thứ tự.

Ví dụCắt rồi ghép xâu

Đề. Xâu dài $n \le 2 \cdot 10^5$, $m \le 2 \cdot 10^5$ thao tác: cắt đoạn $[a, b]$ và dán xuống cuối. In xâu cuối cùng.

Lời giải. Treap ẩn khóa: không có khóa, thứ tự duyệt giữa của cây chính là thứ tự ký tự trong xâu. Cắt đoạn $[a, b]$ là hai lần tách theo số phần tử: $a - 1$ ký tự đầu, rồi $b - a + 1$ ký tự kế. Dán xuống cuối là ghép lại theo thứ tự trái, phải, giữa.

Bước 1: tách theo kích thước. Con trái có ít hơn $k$ nút thì gốc thuộc a, và trong cây con phải chỉ còn cần $k - sz_{lc} - 1$ nút nữa. Không có khóa nào được so sánh. merge giống hệt treap theo khóa, với “mọi phần tử của a đứng trước b” thay cho “khóa nhỏ hơn”.

void split(int t, int k, int &a, int &b) {
    if (!t) {
        a = b = 0;
        return;
    }
    if (sz[lc[t]] < k) a = t, split(rc[t], k - sz[lc[t]] - 1, rc[t], b), pull(a);
    else b = t, split(lc[t], k, a, lc[t]), pull(b);
}

Bước 2: cắt và dán.

split(root, l - 1, a, b);
split(b, r - l + 1, b, c);
root = merge(merge(a, c), b);

Bước 3: đọc lại xâu. Dựng xâu ban đầu bằng cách ghép từng ký tự vào cuối. print duyệt giữa; đệ quy sâu bằng chiều cao, kỳ vọng $O(\log n)$, nên không lo tràn ngăn xếp.

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

const int N = 2e5 + 5;
int tot, root, lc[N], rc[N], sz[N];
unsigned pr[N];
char ch[N];
string res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int newNode(char c) {
    ch[++tot] = c, pr[tot] = rng(), sz[tot] = 1;
    return tot;
}

void pull(int t) {
    sz[t] = 1 + sz[lc[t]] + sz[rc[t]];
}

void split(int t, int k, int &a, int &b) {
    if (!t) {
        a = b = 0;
        return;
    }
    if (sz[lc[t]] < k) a = t, split(rc[t], k - sz[lc[t]] - 1, rc[t], b), pull(a);
    else b = t, split(lc[t], k, a, lc[t]), pull(b);
}

int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (pr[a] > pr[b]) {
        rc[a] = merge(rc[a], b), pull(a);
        return a;
    }
    lc[b] = merge(a, lc[b]), pull(b);
    return b;
}

void print(int t) {
    if (!t) return;
    print(lc[t]);
    res += ch[t];
    print(rc[t]);
}

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

    int n, m;
    string s;
    cin >> n >> m >> s;
    for (char c : s) root = merge(root, newNode(c));
    while (m--) {
        int l, r, a, b, c;
        cin >> l >> r;
        split(root, l - 1, a, b);
        split(b, r - l + 1, b, c);
        root = merge(merge(a, c), b);
    }
    print(root);
    cout << res << '\n';
}

Input7 3
ABCDEFG
2 5
3 4
1 2

OutputCDEGBAF

Mỗi thao tác hai lần tách, hai lần ghép: $O(\log n)$ kỳ vọng.

Nhãn lười: đảo đoạn và thông tin đoạn

Đảo đoạn $[l, r]$: tách ra cây giữa, bật cờ rev ở gốc của nó, ghép lại. Cờ được đẩy xuống khi cần đi vào nút: đổi chỗ hai con và lật cờ của chúng. Mọi hàm đi xuống cây (tách, ghép, duyệt) đều gọi push trước khi đọc con.

Muốn hỏi thông tin của đoạn (tổng, cực đại), mỗi nút giữ thêm giá trị tổng hợp của cả cây con, cập nhật trong pull. Phép đảo không đổi tổng; với thông tin phụ thuộc chiều như tổng tiền tố lớn nhất thì khi đảo cũng phải đổi chỗ phần tiền tố và hậu tố.

Ví dụĐảo các đoạn con

Đề. Xâu dài $n \le 2 \cdot 10^5$, $m \le 2 \cdot 10^5$ lần đảo đoạn $[a, b]$. In xâu cuối cùng.

Lời giải. Treap ẩn khóa như bài trước. Đảo đoạn: tách đoạn ra thành một cây riêng, bật cờ rev ở gốc, ghép lại. Cờ nghĩa là “cả cây con này đang bị đảo nhưng chưa sửa”; chỉ khi cần đi vào nút mới đẩy xuống. rev[b] ^= 1 dùng XOR vì đảo hai lần thì về như cũ.

Bước 1: đẩy cờ. Đảo một cây con là đổi chỗ hai con ở gốc rồi đảo đệ quy từng con; phần đệ quy được hoãn bằng cách lật cờ của hai con.

void push(int t) {
    if (!rev[t]) return;
    swap(lc[t], rc[t]);
    if (lc[t]) rev[lc[t]] ^= 1;
    if (rc[t]) rev[rc[t]] ^= 1;
    rev[t] = 0;
}

Bước 2: mọi hàm đọc con phải đẩy cờ trước. split gọi push trước khi so sz[lc[t]] với $k$: nếu nút còn cờ thì con trái hiện tại thật ra là con phải, đếm theo nó sẽ tách sai đoạn. merge gọi push cho đúng nút sắp bị đổi con (a khi đi vào con phải của nó, b khi đi vào con trái). print gọi push trước khi duyệt con.

if (pr[a] > pr[b]) {
    push(a);
    rc[a] = merge(rc[a], b), pull(a);
    return a;
}
push(b);
lc[b] = merge(a, lc[b]), pull(b);
return b;

Bước 3: một lần đảo.

split(root, l - 1, a, b);
split(b, r - l + 1, b, c);
rev[b] ^= 1;
root = merge(merge(a, b), c);

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

const int N = 2e5 + 5;
int tot, root, lc[N], rc[N], sz[N];
unsigned pr[N];
bool rev[N];
char ch[N];
string res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int newNode(char c) {
    ch[++tot] = c, pr[tot] = rng(), sz[tot] = 1;
    return tot;
}

void pull(int t) {
    sz[t] = 1 + sz[lc[t]] + sz[rc[t]];
}

void push(int t) {
    if (!rev[t]) return;
    swap(lc[t], rc[t]);
    if (lc[t]) rev[lc[t]] ^= 1;
    if (rc[t]) rev[rc[t]] ^= 1;
    rev[t] = 0;
}

void split(int t, int k, int &a, int &b) {
    if (!t) {
        a = b = 0;
        return;
    }
    push(t);
    if (sz[lc[t]] < k) a = t, split(rc[t], k - sz[lc[t]] - 1, rc[t], b), pull(a);
    else b = t, split(lc[t], k, a, lc[t]), pull(b);
}

int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (pr[a] > pr[b]) {
        push(a);
        rc[a] = merge(rc[a], b), pull(a);
        return a;
    }
    push(b);
    lc[b] = merge(a, lc[b]), pull(b);
    return b;
}

void print(int t) {
    if (!t) return;
    push(t);
    print(lc[t]);
    res += ch[t];
    print(rc[t]);
}

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

    int n, m;
    string s;
    cin >> n >> m >> s;
    for (char c : s) root = merge(root, newNode(c));
    while (m--) {
        int l, r, a, b, c;
        cin >> l >> r;
        split(root, l - 1, a, b);
        split(b, r - l + 1, b, c);
        rev[b] ^= 1;
        root = merge(merge(a, b), c);
    }
    print(root);
    cout << res << '\n';
}

Input6 3
ABCDEF
2 5
1 3
4 6

OutputDEAFBC

Mỗi lần đảo $O(\log n)$ kỳ vọng.

Ví dụĐảo đoạn và tính tổng

Đề. Dãy $n \le 2 \cdot 10^5$ số tới $10^9$, $m \le 10^5$ thao tác: đảo đoạn, hoặc in tổng đoạn.

Lời giải. Như bài trước, mỗi nút giữ thêm giá trị val và tổng cây con sum, tính lại trong pull. Đảo đoạn không làm đổi tổng của đoạn, nên cờ đảo không cần sửa sum. Hỏi tổng đoạn là tách đoạn ra thành một cây riêng rồi đọc sum ở gốc của nó.

Bước 1: thêm tổng vào pull. Nút 0 có sum = 0 nên con rỗng không làm sai. Tổng tới $2 \cdot 10^5 \cdot 10^9$ nên sum là long long.

void pull(int t) {
    sz[t] = 1 + sz[lc[t]] + sz[rc[t]];
    sum[t] = val[t] + sum[lc[t]] + sum[rc[t]];
}

push giữ nguyên như bài trước. Nếu đề hỏi thông tin phụ thuộc chiều, như tổng tiền tố lớn nhất, thì push còn phải đổi chỗ phần tiền tố và hậu tố.

Bước 2: hai loại thao tác chung một khuôn. Cả hai đều tách đoạn ra thành b; loại 1 bật cờ, loại 2 in sum[b]; rồi ghép lại đúng thứ tự a, b, c.

split(root, l - 1, a, b);
split(b, r - l + 1, b, c);
if (t == 1) rev[b] ^= 1;
else cout << sum[b] << '\n';
root = merge(merge(a, b), c);

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

const int N = 2e5 + 5;
int tot, root, lc[N], rc[N], sz[N];
unsigned pr[N];
bool rev[N];
ll val[N], sum[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int newNode(ll v) {
    tot++;
    val[tot] = sum[tot] = v, pr[tot] = rng(), sz[tot] = 1;
    return tot;
}

void pull(int t) {
    sz[t] = 1 + sz[lc[t]] + sz[rc[t]];
    sum[t] = val[t] + sum[lc[t]] + sum[rc[t]];
}

void push(int t) {
    if (!rev[t]) return;
    swap(lc[t], rc[t]);
    if (lc[t]) rev[lc[t]] ^= 1;
    if (rc[t]) rev[rc[t]] ^= 1;
    rev[t] = 0;
}

void split(int t, int k, int &a, int &b) {
    if (!t) {
        a = b = 0;
        return;
    }
    push(t);
    if (sz[lc[t]] < k) a = t, split(rc[t], k - sz[lc[t]] - 1, rc[t], b), pull(a);
    else b = t, split(lc[t], k, a, lc[t]), pull(b);
}

int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (pr[a] > pr[b]) {
        push(a);
        rc[a] = merge(rc[a], b), pull(a);
        return a;
    }
    push(b);
    lc[b] = merge(a, lc[b]), pull(b);
    return b;
}

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

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        root = merge(root, newNode(x));
    }
    while (m--) {
        int t, l, r, a, b, c;
        cin >> t >> l >> r;
        split(root, l - 1, a, b);
        split(b, r - l + 1, b, c);
        if (t == 1) rev[b] ^= 1;
        else cout << sum[b] << '\n';
        root = merge(merge(a, b), c);
    }
}

Input6 5
2 1 4 0 3 5
2 1 3
1 2 5
2 2 4
1 1 6
2 4 6

Output7
7
5

Mỗi thao tác $O(\log n)$ kỳ vọng.

Khi thư viện là đủ

Nhiều bài “cây cân bằng” chỉ cần chèn, xóa, tìm phần tử lớn nhất, nhỏ nhất, hay phần tử gần $x$ nhất: set, multiset với lower_bound, upper_bound là cây đỏ đen có sẵn. Xóa một bản trong multiset bằng erase(find(x)), vì erase(x) xóa mọi bản. Cái thư viện chuẩn không có là hạng và phần tử thứ $k$; khi chỉ cần phần tử ở vị trí cố định (như trung vị), giữ hai multiset: nửa nhỏ và nửa lớn, cân bằng kích thước sau mỗi thao tác.

Ví dụTrung vị của cửa sổ

Đề. Mảng $n \le 2 \cdot 10^5$, cửa sổ dài $k$. In trung vị (phần tử thứ $\lceil k/2 \rceil$) của mọi cửa sổ.

Lời giải. Giữ hai multiset: lo chứa $\lceil k/2 \rceil$ phần tử nhỏ nhất của cửa sổ, hi chứa phần còn lại, và mọi phần tử của lo không lớn hơn mọi phần tử của hi. Khi đó trung vị là phần tử lớn nhất của lo.

Bước 1: thêm phần tử mới. Không lớn hơn max của lo thì vào lo, ngược lại vào hi; điều kiện thứ tự được giữ.

if (lo.empty() || a[i] <= *lo.rbegin()) lo.insert(a[i]);
else hi.insert(a[i]);

Bước 2: xóa phần tử rời cửa sổ. Có trong lo và không lớn hơn max của lo thì xóa ở lo, ngược lại ở hi. Giá trị trùng nằm ở hai bên thì xóa bản nào cũng được, vì chúng như nhau. erase(find(x)) chỉ xóa một bản; erase(x) sẽ xóa mọi bản.

int x = a[i - k];
if (lo.find(x) != lo.end() && x <= *lo.rbegin()) lo.erase(lo.find(x));
else hi.erase(hi.find(x));

Bước 3: cân bằng. lo thừa thì chuyển max của nó sang hi; thiếu thì lấy min của hi sang. Phần tử chuyển đi luôn ở biên, nên điều kiện thứ tự vẫn đúng. Trong $k - 1$ bước đầu cửa sổ chưa đủ, balance vẫn chạy nhưng không in.

void balance() {
    while ((int)lo.size() > (k + 1) / 2) {
        hi.insert(*lo.rbegin());
        lo.erase(prev(lo.end()));
    }
    while ((int)lo.size() < (k + 1) / 2 && !hi.empty()) {
        lo.insert(*hi.begin());
        hi.erase(hi.begin());
    }
}

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

const int N = 2e5 + 5;
int n, k, a[N];
multiset<int> lo, hi;

void balance() {
    while ((int)lo.size() > (k + 1) / 2) {
        hi.insert(*lo.rbegin());
        lo.erase(prev(lo.end()));
    }
    while ((int)lo.size() < (k + 1) / 2 && !hi.empty()) {
        lo.insert(*hi.begin());
        hi.erase(hi.begin());
    }
}

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (lo.empty() || a[i] <= *lo.rbegin()) lo.insert(a[i]);
        else hi.insert(a[i]);
        if (i > k) {
            int x = a[i - k];
            if (lo.find(x) != lo.end() && x <= *lo.rbegin()) lo.erase(lo.find(x));
            else hi.erase(hi.find(x));
        }
        balance();
        if (i >= k) cout << *lo.rbegin() << ' ';
    }
    cout << '\n';
}

Input7 4
8 1 5 2 9 3 6

Output2 2 3 3

$O(n \log k)$.