Splay Tree

Splay Tree (cây splay) là cây nhị phân tìm kiếm (BST) tự điều chỉnh: sau mỗi lần truy cập một node, ta xoay node đó dần lên cho tới khi nó trở thành gốc — thao tác này gọi là splay. Nhờ vậy cây không cần lưu bất kỳ thông tin cân bằng nào (chiều cao, màu, hệ số...) mà vẫn đảm bảo mọi thao tác (tìm, chèn, xoá, tách, ghép) chạy trong $O(\log N)$ khấu hao (amortized).

Điểm mạnh thật sự của Splay Tree với competitive programming không nằm ở việc thay thế std::set, mà ở khả năng thao tác trên dãy động (dynamic sequence): đảo ngược một đoạn, cộng giá trị lên một đoạn, cắt một đoạn dán đi nơi khác, chèn/xoá ở giữa — tất cả trong $O(\log N)$, điều mà mảng thường hay segment tree tĩnh không làm được. Đây là lý do Splay Tree (cùng Treap) là nền tảng để cài Link-Cut Tree.

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

Vì sao "đưa node lên gốc" lại tốt? Trực giác đến từ tính cục bộ (locality): trong các bài toán thực tế, node vừa truy cập rất có thể sẽ được truy cập lại sớm. Splay đưa nó lên gốc nên lần sau chạm tới nó gần như tức thì. Quan trọng hơn, thao tác splay không xoay "ngây thơ" từng bước một, mà theo cặp (zig-zig / zig-zag) — chính cách xoay theo cặp này làm chiều cao cây giảm đi một nửa dọc theo đường đi mỗi lần splay, nên những đường đi dài (tốn kém) tự động bị "san phẳng" cho các lần sau.

Phân tích khấu hao bằng hàm thế năng $\Phi ={\sum }_x\log (\text{size}(x))$ chứng minh: một thao tác có thể tốn nhiều, nhưng nó đồng thời làm giảm thế năng tương ứng, nên trung bình mỗi thao tác chỉ tốn $O(\log N)$. Đây là lý do ta nói $O(\log N)$ amortized chứ không phải worst-case từng thao tác.

Thao tác splay đưa node $x$ lên gốc dựa trên quan hệ giữa $x$, cha $p$ và ông $g$:

• Zig — $x$ là con của gốc ($p$ là gốc): chỉ cần một phép xoay $x$.
• Zig-Zig — $x$ và $p$ cùng chiều (cùng là con trái, hoặc cùng là con phải): xoay $p$ trước, rồi xoay $x$.
• Zig-Zag — $x$ và $p$ khác chiều: xoay $x$ hai lần.

Phân biệt zig-zig với "xoay $x$ hai lần" là điều cốt lõi — nếu zig-zig mà xoay $x$ hai lần (sai), cây có thể suy biến thành dây xích và mất luôn tính $O(\log N)$ amortized.

Khoá ngầm (implicit key). Khi dùng cho dãy, ta KHÔNG so sánh theo giá trị mà theo vị trí trong dãy. Vị trí của một node = số node nằm bên trái nó (theo thứ tự duyệt trung tự — in-order). Vì vậy mỗi node lưu sz = kích thước cây con; từ đó ta tìm được "phần tử thứ $k$". Mọi thao tác đoạn $[l,r]$ đều quy về một mẫu: tách lấy đúng cây con chứa đoạn đó, xử lý ở gốc cây con, rồi ghép lại.

Ví dụ chạy tay

Xét dãy A B C D E (5 phần tử) lưu trong Splay Tree theo khoá ngầm, ta muốn đảo ngược đoạn $[2,4]$ (tức B C D → D C B), kết quả mong đợi: A D C B E.

Giả sử cây hiện tại (in-order đọc ra đúng A B C D E), mỗi node ghi kèm sz:

            C(sz=5)
           /      \
        B(2)       D(2)
        /            \
      A(1)           E(1)

Bước 1 — Để cô lập đoạn $[2,4]$, ta đưa node ngay trước đoạn (vị trí 1 = A) lên gốc, và đưa node ngay sau đoạn (vị trí 5 = E) lên làm con phải của gốc. Splay A lên gốc:

   A(5)
      \
       C(4)
      /    \
    B(1)    D(2)
              \
               E(1)

Bước 2 — Splay E tới ngay dưới A (goal = A). Khi đó con trái của E chính là cây con chứa đúng đoạn B C D:

   A(5)
      \
       E(4)
      /
    C(3)        <- gốc cây con của đoạn [2,4], đánh dấu cần đảo
   /   \
 B(1)  D(1)

Bước 3 — Gắn cờ rev (lazy reverse) lên node C. Cờ này nghĩa là: cây con gốc C cần được đọc ngược lại. Khi push_down(C) về sau, ta đổi chỗ con trái/con phải và truyền cờ xuống:

   sau khi đẩy cờ rev xuống C:

       C
      / \
    D     B      <- con trái và phải đã hoán đổi

Đọc in-order toàn cây bây giờ: A → (cây con đã đảo: D C B) → E = A D C B E. Đúng kết quả.

Mấu chốt: ta KHÔNG đảo từng phần tử (sẽ là $O(N)$) mà chỉ gắn một cờ lazy lên gốc cây con — $O(\log N)$.

Cài đặt

Cài đặt Splay Tree khoá ngầm hỗ trợ: đảo đoạn (rev), cộng đoạn (lazy), tính tổng đoạn (sum), tách (split) và ghép (merge).

const int MAXN = 2e5 + 5;

struct Node {
    int ch[2], par, sz;        // con trái/phải, cha, kích thước cây con
    long long val, sum, lazy;  // giá trị node, tổng cây con, lazy cộng đoạn
    bool rev;                  // cờ lazy đảo đoạn
} t[MAXN];
int root, tot;

// Cập nhật sz và sum của x từ hai con (gọi sau khi con thay đổi)
void push_up(int x) {
    t[x].sz  = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + 1;
    t[x].sum = t[t[x].ch[0]].sum + t[t[x].ch[1]].sum + t[x].val;
}

// Đánh dấu "đảo" cho x: hoán đổi hai con, lật cờ rev (lazy)
void apply_rev(int x) {
    swap(t[x].ch[0], t[x].ch[1]);
    t[x].rev ^= 1;
}

// Đánh dấu "cộng v lên toàn cây con x": cập nhật val, sum, dồn lazy
void apply_add(int x, long long v) {
    t[x].val += v;
    t[x].sum += (long long)t[x].sz * v;
    t[x].lazy += v;
}

// Đẩy các lazy của x xuống hai con TRƯỚC khi đi xuống chúng
void push_down(int x) {
    if (t[x].rev) {
        if (t[x].ch[0]) apply_rev(t[x].ch[0]);
        if (t[x].ch[1]) apply_rev(t[x].ch[1]);
        t[x].rev = 0;
    }
    if (t[x].lazy) {
        if (t[x].ch[0]) apply_add(t[x].ch[0], t[x].lazy);
        if (t[x].ch[1]) apply_add(t[x].ch[1], t[x].lazy);
        t[x].lazy = 0;
    }
}

// x có phải là gốc của cây (theo nghĩa cha không nhận x làm con)?
bool is_root(int x) { return t[t[x].par].ch[0] != x && t[t[x].par].ch[1] != x; }
// x là con phải (1) hay con trái (0) của cha?
bool dir(int x)     { return t[t[x].par].ch[1] == x; }

// Xoay x lên thay thế vị trí của cha p
void rotate(int x) {
    int p = t[x].par, g = t[p].par, d = dir(x);
    if (!is_root(p)) t[g].ch[dir(p)] = x;   // nối ông với x
    t[x].par = g;
    t[p].ch[d] = t[x].ch[!d];               // con đối diện của x chuyển sang cho p
    if (t[x].ch[!d]) t[t[x].ch[!d]].par = p;
    t[x].ch[!d] = p; t[p].par = x;          // p trở thành con của x
    push_up(p); push_up(x);                 // p ở dưới nên cập nhật trước
}

// Đẩy lazy dọc đường từ gốc xuống x (đệ quy từ trên xuống)
void push_all(int x) {
    if (!is_root(x)) push_all(t[x].par);
    push_down(x);
}

// Đưa x lên gốc (hoặc lên ngay dưới node goal nếu goal != 0)
void splay(int x, int goal = 0) {
    push_all(x);                            // đẩy lazy trước khi xoay, nếu không sẽ sai
    while (t[x].par != goal && !is_root(x)) {
        int p = t[x].par;
        if (t[p].par != goal && !is_root(p))
            rotate(dir(x) == dir(p) ? p : x); // zig-zig: xoay p trước; zig-zag: xoay x
        rotate(x);
    }
    if (!goal) root = x;
}

// Tìm node ở vị trí thứ k (1-based) theo in-order
int kth(int k) {
    int x = root;
    while (true) {
        push_down(x);                       // luôn đẩy lazy trước khi rẽ hướng
        int lsz = t[t[x].ch[0]].sz;
        if (lsz + 1 == k) return x;
        if (k <= lsz) x = t[x].ch[0];
        else { k -= lsz + 1; x = t[x].ch[1]; }
    }
}

// Lấy gốc cây con đại diện cho đoạn [l, r] (1-based) lên đúng vị trí truy cập:
// splay node (l-1) lên gốc, splay node (r+1) lên dưới gốc;
// khi đó con trái của (r+1) chính là đoạn [l, r].
// (Thường thêm 2 node lính canh ở hai đầu để l-1 và r+1 luôn tồn tại.)
int range(int l, int r) {
    int a = kth(l - 1);  splay(a);
    int b = kth(r + 1);  splay(b, a);
    return t[b].ch[0];
}

// Tách: chia dãy thành [1..k] và [k+1..n], trả về (gốc trái, gốc phải)
pair<int,int> split(int k) {
    if (k == 0) return {0, root};
    if (k == t[root].sz) return {root, 0};
    int x = kth(k + 1); splay(x);
    int L = t[x].ch[0];
    t[x].ch[0] = 0; t[L].par = 0;           // cắt rời cây con trái
    push_up(x);
    return {L, x};
}

// Ghép hai cây L, R (mọi vị trí trong L đứng trước mọi vị trí trong R)
int merge(int L, int R) {
    if (!L) return R;
    if (!R) return L;
    root = L;
    int x = kth(t[L].sz); splay(x);         // đưa phần tử cuối của L lên gốc
    t[x].ch[1] = R; t[R].par = x;           // R trở thành con phải
    push_up(x);
    return x;
}

Mẫu sử dụng (đảo đoạn $[l,r]$, có dùng 2 node lính canh nên vị trí thật là $l+1\dots r+1$):

int seg = range(l, r);   // lấy gốc cây con của đoạn
apply_rev(seg);          // gắn cờ đảo — O(log N), không duyệt từng phần tử

Độ phức tạp

Vì sao $O(\log N)$ amortized chứ không phải worst-case? Một thao tác đơn lẻ có thể chạm vào cả đường đi dài $O(N)$. Nhưng chính việc splay đó "san phẳng" đường đi, làm giảm thế năng $\Phi$, nên chi phí được "trả trước" cho các thao tác sau. Trung bình cộng dồn $m$ thao tác là $O((m+N)\log N)$.

Bộ nhớ: $O(N)$ — mỗi phần tử là một node với số trường hằng (con, cha, sz, val, sum, lazy, rev). Dùng mảng cấp phát sẵn (như trên) nhanh và tránh phân mảnh so với new.

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

• Quên push_down trước khi đi xuống / trước khi splay. Trong splay, phải gọi push_all(x) đẩy hết lazy dọc từ gốc xuống $x$ trước vòng xoay; trong kth phải push_down(x) trước khi rẽ trái/phải. Quên bước này khiến lazy (rev/add) "đông cứng" ở vị trí cũ trong khi cấu trúc đã đổi → kết quả sai khó lần.

• Sai thứ tự push_up trong rotate. Sau khi xoay, node $p$ (đã thành con của $x$) phải push_up(p) trước, rồi mới push_up(x), vì sz/sum của $x$ phụ thuộc vào $p$. Đảo thứ tự → sz/sum ở gốc sai → kth trả vị trí lệch.

• Tràn số (overflow) ở sum. Với $n,x_i\le {10}^9$ thì tổng cả dãy tới $~2·{10}^{14}$, vượt int (giới hạn $~2,1·{10}^9$). Phải để sum, val, lazy kiểu long long, và ép kiểu khi nhân: (long long)t[x].sz * v. Đề elderwand còn ghi rõ "tổng có thể vượt $2^{31}-1$" — cố tình bẫy int.

• Nhầm zig-zig thành "xoay $x$ hai lần". Trường hợp $x$, $p$ cùng chiều phải xoay $p$ trước (rotate(p); rotate(x);). Nếu xoay $x$ hai lần, cây có thể suy biến thành dây xích, độ phức tạp khấu hao $O(\log N)$ không còn đúng → TLE trên test lớn.

• Sai biên khi cô lập đoạn $[l,r]$. Mẫu chuẩn cần node $l-1$ và $r+1$ tồn tại. Với $l=1$ hoặc $r=n$, hai vị trí này ra ngoài dãy. Cách an toàn: thêm hai node lính canh (sentinel) ở đầu và cuối dãy, khi đó vị trí thật của phần tử $i$ là $i+1$. Quên lính canh → truy cập kth(0) hoặc kth(n+1) gây lỗi.

• Quên cập nhật t[L].par = 0 khi tách. Sau khi cắt cây con trái trong split, phải đặt cha của gốc cây con cũ về 0. Nếu không, is_root của nó vẫn trỏ ngược lên cây cũ, lần splay sau leo nhầm lên cây đã tách → hỏng cấu trúc.

Biến thể / Mở rộng

• Link-Cut Tree (LCT). Dùng nhiều Splay Tree làm cây phụ trợ để biểu diễn các "đường ưa thích (preferred path)" trên rừng động, hỗ trợ nối/cắt cạnh và truy vấn đường đi trong $O(\log N)$ amortized. Bài elderwand chính là LCT. Xem thêm Link-Cut Tree.
• Treap (cây ngẫu nhiên). Cùng giải lớp bài "dãy động" này; Treap dễ cài hằng số ổn định, Splay không cần sinh số ngẫu nhiên và tận dụng tính cục bộ tốt hơn. Xem Treap.
• Order statistics / rank. Nhờ trường sz, Splay Tree làm được "phần tử thứ $k$" và "có bao nhiêu phần tử nhỏ hơn $v$" trong $O(\log N)$.

Bài tập luyện

• Đảo Ngược Đoạn Con (subreverse) — (Expert) Chỉ đảo đoạn $[a,b]$ của một xâu rồi in kết quả; bài nhập môn cờ lazy rev trên Splay khoá ngầm.
• Đảo Ngược và Tổng Đoạn (revsums) — (Expert) Trộn đảo đoạn với truy vấn tổng đoạn, buộc kết hợp đúng rev + push_up(sum) (và cẩn thận overflow long long).
• Cắt và Dán (cutpaste) — (Expert) Cắt đoạn $[a,b]$ dán vào cuối — luyện thẳng cặp thao tác split + merge, đặc sản của Splay/Treap mà segment tree không làm được.
• Truy vấn Đoạn và Sao chép (rngcopy) — (Veteran) Quản lý nhiều dãy với thao tác sao chép cả dãy cùng cập nhật/tổng đoạn; nâng cấp tư duy quản lý nhiều gốc cây cân bằng.
• Cây Đũa Phép Cơm Nguội (elderwand) — (Expert) Nối/cắt cạnh và truy vấn tổng trên đường đi của rừng động — chính là Link-Cut Tree, đỉnh cao ứng dụng của Splay Tree.