$$\LARGE{\color{purple}{\mathbf{Note-算法进阶课} } }$$
Splay树
Splay树是一种平衡树,在拥有平衡树的功能的同时,还可以进行一些区间维护操作(比如:区间反转)
维护有序性: Splay 树通过维护树的整体中序遍历保持顺序来保证支持查找前驱,后继,kth,rk基本操作
Splay拥有两个基础函数:rotate,splay,其余操作建立在这两个的基础之上
1. rotate
{:height=”80%” width=”80%”class=”img-responsive”}
在实现这个 rotate 操作时,我们可以用一个函数同时实现左旋与右旋
无论是左旋与右旋 我们都要处理三条边的转换
\begin{align}
&Z- Y \Leftrightarrow Z-X\\
&Y- X \Leftrightarrow X-Y\\
&X- B \Leftrightarrow Y-B\\
\end{align}
于是可以把 rotaote 写成:
void rotate(int x)
{
int y = tr[x].p;
int z = tr[y].p;
int k = tr[y].s[1] == x;
// k=0表示x是y的左儿子;k=1表示x是y的右儿子
// 1. z-y --- z-x
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
// 3. x-b -- y-b
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
// 2. y-x --- x-y
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);// y在下面先pushup
}
2. splay
splay(x,k) 操作: 将节点 $x$ 伸展到 $k$ 的下面
通常我们在查询某个节点,会将其伸展到根节点,据严谨证明(这里没有证明)这是保证 Splay 树在任何数据做到平均 $O(\log n)$的关键
{:height=”80%” width=”80%”class=”img-responsive”}
Case1. : 如果是斜的直线,需要先转 $y$,再转 $x$
Case2. : 如果是折线,需要转两次 $x$
经过每次将 $x$ 往上挪两个节点,最终能将 $x$ 挪到 $k$ 下面
void splay(int x, int k)
{
while (tr[x].p != k)
{
int y = tr[x].p, z = tr[y].p;
if (z != k)
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
if (!k) root = x;
}
下面介绍一些其他操作:
3. 插入操作/删除
3.1 单点插入
这个只需要按照关键字,找到新节点应该插入的位置,然后直接插入节点
void insert(int v)
{
int u = root, p = 0;
while (u) p = u, u = tr[u].s[v > tr[u].v];
u = ++ idx;
if (p) tr[p].s[v > tr[p].v] = u;
tr[u].init(v, p);
splay(u, 0);
}
3.1 区间插入
在 $\[L,R]$ 之间插入一段序列:
可以先 splay(L,0)(将 L 变为根节点),再 splay(R,L)(将 R 变为根节点下面一个节点)
将待插入序列构造成一株平衡的二叉树插入到 $R$ 节点的左儿子
删除操作是类似的
Splay树如何维护信息
1. pushup 维护懒标记之外的信息
利用两个子节点的信息计算根节点的信息
放置位置: rotate函数的最后
2. pushdown 维护懒标记
下传懒标记
放置位置:在所有递归之前都要有 pushdown
splay
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 100010;
struct Node
{
int s[2],p,v;
int sz,lazy;
void init(int _v,int _p)
{
p = _p,v = _v,sz = 1;
}
}tr[N];
int root,idx,n,q;
void pushup(int u)
{
tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + 1;
}
int build(int l,int r,int p)
{
int mid = l + r >> 1;
int u = ++ idx;
tr[u].init(mid,p);
if(l < mid) tr[u].s[0] = build(l,mid - 1,u);
if(r > mid) tr[u].s[1] = build(mid + 1,r,u);
pushup(u);
return u;
}
void pushdown(int u)
{
if(tr[u].lazy)
{
swap(tr[u].s[0],tr[u].s[1]);
tr[tr[u].s[0]].lazy ^= 1;
tr[tr[u].s[1]].lazy ^= 1;
tr[u].lazy = 0;
}
}
void rotate(int x)
{
int y = tr[x].p,z = tr[y].p;
int k = (x == tr[y].s[1]);
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y),pushup(x);
}
void splay(int x,int k)
{
while(tr[x].p != k)
{
int y = tr[x].p,z = tr[y].p;
if(z != k)
{
if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root = x;
}
void insert(int x)
{
int u = root,p = 0;
while(u) p = u,u = tr[u].s[x > tr[u].v];
u = ++ idx;
if(p) tr[p].s[x > tr[p].v] = u;
tr[u].init(x,p);
splay(x,0);
}
int kth(int k)
{
int u = root;
while(u)
{
pushdown(u);
if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
else if(tr[tr[u].s[0]].sz + 1 == k) return u;
else k -= tr[tr[u].s[0]].sz + 1,u = tr[u].s[1];
}
return -1;
}
void output(int u)
{
pushdown(u);
if(tr[u].s[0]) output(tr[u].s[0]);
if(tr[u].v >= 1 && tr[u].v <= n) cout << tr[u].v << " ";
if(tr[u].s[1]) output(tr[u].s[1]);
}
int main()
{
fastio();
cin >> n >> q;
root = build(0,n + 1,0);// 0与n+1是哨兵节点
while(q -- )
{
int l,r;cin >> l >> r;
int L = kth(l),R = kth(r + 2);
splay(L,0),splay(R,L);
tr[tr[R].s[0]].lazy ^= 1;
}
output(root);
return 0;
}