Splay tree is a self-adjusting binary search tree introduced by Daniel Sleator and Robert Tarjan. Unlike Treap which assigns random priorities to nodes, Splay tree performs rotations to move accessed nodes to the root, thereby maintaining balance during operations.
Core Operations
Node Clearing
Reset all fields of a node to zero:
void clear(int node) {
son[node][0] = son[node][1] = size[node] = val[node] = cnt[node] = fa[node] = 0;
}
Size Update
Recalculate subtree sizes for a given node:
void update(int node) {
if (node) {
size[node] = cnt[node];
if (son[node][0]) {
size[node] += size[son[node][0]];
}
if (son[node][1]) {
size[node] += size[son[node][1]];
}
}
}
Child Determination
Determine whether a node is a left or right child:
bool get(int node) {
return son[fa[node]][1] == node;
}
Rotation Operation
Perform a single rotation between a node and its parent:
void rotate(int node) {
int parent = fa[node], grandparent = fa[parent], direction = get(node);
son[parent][direction] = son[node][direction ^ 1];
fa[son[parent][direction]] = parent;
son[node][direction ^ 1] = parent;
fa[parent] = node;
fa[node] = grandparent;
if (grandparent) {
son[grandparent][son[grandparent][1] == parent] = node;
}
update(parent);
update(node);
}
Splay Operation
Move a node to the root through a series of rotations:
void splay(int node, int target_parent) {
for (int parent; (parent = fa[node]) != target_parent; rotate(node)) {
if (fa[parent] != target_parent) {
rotate(get(node) == get(parent) ? parent : node);
}
}
if (!target_parent) {
root = node;
}
}
Insertion
Add a new element to the tree:
void insert(int value) {
if (root == 0) {
tot++;
val[tot] = value;
cnt[tot] = size[tot] = 1;
son[tot][0] = son[tot][1] = fa[tot] = 0;
root = tot;
return;
}
int current = root, previous = 0;
while (true) {
if (value == val[current]) {
cnt[current]++;
update(current);
update(previous);
splay(current);
break;
}
previous = current;
current = son[current][value > val[current]];
if (current == 0) {
tot++;
fa[tot] = previous;
son[tot][0] = son[tot][1] = 0;
son[previous][value > val[previous]] = tot;
cnt[tot] = size[tot] = 1;
val[tot] = value;
update(previous);
splay(tot);
break;
}
}
}
Rank Query
Determine the position of an element in sorted order:
int rank(int value) {
int current = root, result = 0;
while (true) {
if (!current) return result + 1;
if (value < val[current]) {
current = son[current][0];
} else {
if (son[current][0]) {
result += size[son[current][0]];
}
if (value == val[current]) {
splay(current);
return result + 1;
}
result += cnt[current];
current = son[current][1];
}
}
}
Element Retrieval
Find the element at a specified rank:
int find(int position) {
int current = root;
while (true) {
if (son[current][0] && position <= size[son[current][0]]) {
current = son[current][0];
} else {
int count = (son[current][0] ? size[son[current][0]] : 0) + cnt[current];
if (position <= count) {
return val[current];
}
position -= count;
current = son[current][1];
}
}
}
Predecessor and Successor
Locate the immediate smaller and larger elements:
int predecessor() {
int current = son[root][0];
while (son[current][1]) {
current = son[current][1];
}
return current;
}
int successor() {
int current = son[root][1];
while (son[current][0]) {
current = son[current][0];
}
return current;
}
Deletion
Remove one occurrence of a value:
void remove(int value) {
rank(value);
if (cnt[root] > 1) {
cnt[root]--;
update(root);
return;
}
if (!son[root][0] && !son[root][1]) {
clear(root);
root = 0;
return;
}
if (!son[root][0]) {
int old_root = root;
root = son[root][1];
fa[root] = 0;
clear(old_root);
return;
}
if (!son[root][1]) {
int old_root = root;
root = son[root][0];
fa[root] = 0;
clear(old_root);
return;
}
int pred = predecessor(), old_root = root;
splay(pred);
son[root][1] = son[old_root][1];
fa[son[old_root][1]] = root;
clear(old_root);
update(root);
}
Example Implementation
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 5;
int n, root, tot;
int fa[maxn], son[maxn][2];
int cnt[maxn], val[maxn], size[maxn];
void clear(int x) {
son[x][0] = son[x][1] = size[x] = val[x] = cnt[x] = fa[x] = 0;
}
bool get(int x) {
return son[fa[x]][1] == x;
}
void update(int x) {
if (x) {
size[x] = cnt[x];
if (son[x][0]) {
size[x] += size[son[x][0]];
}
if (son[x][1]) {
size[x] += size[son[x][1]];
}
}
}
void rotate(int x) {
int y = fa[x], z = fa[y], k = get(x);
son[y][k] = son[x][k ^ 1];
fa[son[y][k]] = y;
son[x][k ^ 1] = y;
fa[y] = x;
fa[x] = z;
if (z) {
son[z][son[z][1] == y] = x;
}
update(y);
update(x);
}
void splay(int x) {
for (int f = 0; (f = fa[x]); rotate(x)) {
if (fa[f]) {
rotate((get(x) == get(f)) ? f : x);
}
}
root = x;
}
void insert(int x) {
if (root == 0) {
tot++;
val[tot] = x;
cnt[tot] = size[tot] = 1;
son[tot][0] = son[tot][1] = fa[tot] = 0;
root = tot;
return;
}
int u = root, f = 0;
while (true) {
if (x == val[u]) {
cnt[u]++;
update(u);
update(f);
splay(u);
break;
}
f = u;
u = son[u][x > val[u]];
if (u == 0) {
tot++;
fa[tot] = f;
son[tot][0] = son[tot][1] = 0;
son[f][x > val[f]] = tot;
cnt[tot] = size[tot] = 1;
val[tot] = x;
update(f);
splay(tot);
break;
}
}
}
int rank(int x) {
int u = root, ans = 0;
while (true) {
if (!u) return ans + 1;
if (x < val[u]) {
u = son[u][0];
} else {
if (son[u][0]) {
ans += size[son[u][0]];
}
if (x == val[u]) {
splay(u);
return ans + 1;
}
ans += cnt[u];
u = son[u][1];
}
}
}
int find(int x) {
int u = root;
while (true) {
if (son[u][0] && x <= size[son[u][0]]) {
u = son[u][0];
} else {
int sz = (son[u][0] ? size[son[u][0]] : 0) + cnt[u];
if (x <= sz) {
return val[u];
}
x -= sz;
u = son[u][1];
}
}
}
int pre() {
int u = son[root][0];
while (son[u][1]) {
u = son[u][1];
}
return u;
}
int nxt() {
int u = son[root][1];
while (son[u][0]) {
u = son[u][0];
}
return u;
}
void del(int x) {
rank(x);
if (cnt[root] > 1) {
cnt[root]--;
update(root);
return;
}
if (!son[root][0] && !son[root][1]) {
clear(root);
root = 0;
return;
}
if (!son[root][0]) {
int rt = root;
root = son[root][1];
fa[root] = 0;
clear(rt);
return;
}
if (!son[root][1]) {
int rt = root;
root = son[root][0];
fa[root] = 0;
clear(rt);
return;
}
int p = pre(), rt = root;
splay(p);
son[root][1] = son[rt][1];
fa[son[rt][1]] = root;
clear(rt);
update(root);
}
int main() {
int opt, x;
scanf("%d", &n);
while (n--) {
scanf("%d%d", &opt, &x);
if (opt == 1) {
insert(x);
} else if (opt == 2) {
del(x);
} else if (opt == 3) {
printf("%d\n", rank(x));
} else if (opt == 4) {
printf("%d\n", find(x));
} else if (opt == 5) {
insert(x);
printf("%d\n", val[pre()]);
del(x);
} else {
insert(x);
printf("%d\n", val[nxt()]);
del(x);
}
}
return 0;
}
Advanced Applications
Interval Reversal
Implement a data structure that supports reversing intervals using Splay trees:
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, root, tot;
int a[maxn], val[maxn], fa[maxn], lazy[maxn];
int son[maxn][2], size[maxn];
bool get(int x) {
return son[fa[x]][1] == x;
}
void update(int x) {
if (x) {
size[x] = 1;
if (son[x][0]) {
size[x] += size[son[x][0]];
}
if (son[x][1]) {
size[x] += size[son[x][1]];
}
}
}
void push_down(int x) {
if (x && lazy[x]) {
lazy[son[x][0]] ^= 1;
lazy[son[x][1]] ^= 1;
swap(son[x][0], son[x][1]);
lazy[x] = 0;
}
}
void rotate(int x) {
int y = fa[x], z = fa[y], k = get(x);
son[y][k] = son[x][k ^ 1];
fa[son[y][k]] = y;
son[x][k ^ 1] = y;
fa[y] = x;
fa[x] = z;
if (z) {
son[z][son[z][1] == y] = x;
}
update(y);
update(x);
}
void splay(int x, int goal) {
for (int f; (f = fa[x]) != goal; rotate(x)) {
if (fa[f] != goal) {
rotate(get(f) == get(x) ? f : x);
}
}
if (goal == 0) {
root = x;
}
}
int build(int l, int r, int f) {
if (l > r) {
return 0;
}
int mid = (l + r) / 2;
int now = ++tot;
fa[now] = f;
son[now][0] = son[now][1] = 0;
val[now] = a[mid];
size[now] = 1;
son[now][0] = build(l, mid - 1, now);
son[now][1] = build(mid + 1, r, now);
update(now);
return now;
}
int find(int x) {
int now = root;
while (true) {
push_down(now);
if (x <= size[son[now][0]]) {
now = son[now][0];
} else {
x -= (size[son[now][0]] + 1);
if (!x) {
return now;
}
now = son[now][1];
}
}
}
void reverse(int x, int y) {
int l = x - 1, r = y + 1;
l = find(l);
r = find(r);
splay(l, 0);
splay(r, l);
int now = son[root][1];
now = son[now][0];
lazy[now] ^= 1;
}
void dfs(int now) {
push_down(now);
if (son[now][0]) {
dfs(son[now][0]);
}
if (val[now] != inf && val[now] != -inf) {
printf("%d ", val[now]);
}
if (son[now][1]) {
dfs(son[now][1]);
}
}
int main() {
int l, r;
scanf("%d%d", &n, &m);
a[1] = -inf;
for (int i = 1; i <= n; i++) {
a[i + 1] = i;
}
a[n + 2] = inf;
root = build(1, n + 2, 0);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &l, &r);
reverse(l + 1, r + 1);
}
dfs(root);
return 0;
}
Interval Insertion Problem
Solve sequence manipulation tasks involving moving elements within intervals:
#include <cstdio>
using namespace std;
const int maxn = 2e6 + 5;
int n, m, root, tot;
int a[maxn], size[maxn], son[maxn][2];
int fa[maxn], val[maxn], pos[maxn], cnt[maxn];
char opt[maxn];
void clear(int x)
{
size[x] = son[x][0] = son[x][1] = fa[x] = cnt[x] = 0;
pos[val[x]] = 0, val[x] = 0;
}
bool get(int x)
{
return son[fa[x]][1] == x;
}
void push_up(int x)
{
if (x)
{
size[x] = cnt[x];
if (son[x][0])
size[x] += size[son[x][0]];
if (son[x][1])
size[x] += size[son[x][1]];
}
}
void rotate(int x)
{
int y = fa[x], z = fa[y], k = get(x);
son[y][k] = son[x][k ^ 1];
fa[son[y][k]] = y;
son[x][k ^ 1] = y;
fa[y] = x;
fa[x] = z;
if (z)
son[z][son[z][1] == y] = x;
push_up(y);
push_up(x);
}
void splay(int x, int goal)
{
for (int f; (f = fa[x]) != goal; rotate(x))
if (fa[f] != goal)
rotate(get(x) == get(f) ? f : x);
if (!goal)
root = x;
}
int build(int l, int r, int f)
{
if (l > r)
return 0;
int mid = (l + r) / 2, u = ++tot;
fa[u] = f;
size[u] = cnt[u] = 1;
val[u] = a[mid];
pos[a[mid]] = u;
son[u][0] = build(l, mid - 1, u);
son[u][1] = build(mid + 1, r, u);
push_up(u);
return u;
}
int pre()
{
int u = son[root][0];
while (son[u][1])
u = son[u][1];
return u;
}
int rank(int x)
{
splay(pos[x], 0);
return size[son[root][0]] + 1;
}
int find(int x)
{
int u = root;
while (true)
{
if (son[u][0] && x <= size[son[u][0]])
u = son[u][0];
else
{
int sz = (son[u][0] ? size[son[u][0]] : 0) + cnt[u];
if (x <= sz)
return u;
x -= sz;
u = son[u][1];
}
}
}
void del(int x)
{
rank(x);
if (cnt[root] > 1)
{
cnt[root]--;
push_up(root);
return;
}
else if (!son[root][0] && !son[root][1])
{
clear(root);
root = 0;
return;
}
else if (!son[root][1])
{
int rt = root;
root = son[root][0];
fa[root] = 0;
clear(rt);
return;
}
else if (!son[root][0])
{
int rt = root;
root = son[root][1];
fa[root] = 0;
clear(rt);
return;
}
else
{
int p = pre(), rt = root;
splay(p, 0);
son[root][1] = son[rt][1];
fa[son[root][1]] = root;
clear(rt);
push_up(root);
return;
}
}
void update(int idx, int value)
{
int x = find(idx), y = find(idx - 1);
splay(x, 0);
splay(y, x);
son[y][1] = ++tot;
fa[tot] = y;
size[tot] = cnt[tot] = 1;
son[tot][0] = son[tot][1] = 0;
val[tot] = value;
pos[value] = tot;
push_up(y);
push_up(x);
}
int main()
{
int s, t, x;
scanf("%d%d", &n, &m);
a[1] = 0;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i + 1]);
a[n + 2] = n + 1;
root = build(1, n + 2, 0);
for (int i = 1; i <= m; i++)
{
scanf("%s", opt);
if (opt[0] == 'T')
{
scanf("%d", &s);
del(s);
update(2, s);
}
else if (opt[0] == 'B')
{
scanf("%d", &s);
del(s);
update(n + 1, s);
}
else if (opt[0] == 'I')
{
scanf("%d%d", &s, &t);
x = rank(s);
del(s);
update(x + t, s);
}
else if (opt[0] == 'A')
{
scanf("%d", &s);
printf("%d\n", rank(s) - 2);
}
else
{
scanf("%d", &s);
printf("%d\n", val[find(s + 1)]);
}
}
return 0;
}