Loading... ## 定义 ```cpp template < typename Key >struct Splay ; ``` `Splay` 是关联容器，含有 `key` 类型对象的已排序集。用比较函数`less<Key>`进行排序。搜索、移除和插入拥有对数复杂度。 `Splay` 以Splay树实现。 ### 成员类型 | 成员类型 | 定义 | | ------------ | ----- | | `value_type` | `Key` | ### 成员 | 分类或标识符 | 描述 | | ------------------------------------------------------------ | ------------------------------------------------------------ | | **常规** | | | 构造函数 | 构造 `Splay` (公开成员函数) | | 析构函数 | 析构 `Splay` (公开成员函数) | | **容量** | | | empty | 检查是否为空 (公开成员函数) | | size | 返回容纳的元素数 (公开成员函数) | | **修改器** | | | clear | 清除内容(公开成员函数) | | ins | 插入结点(公开成员函数) | | del | 擦除元素(公开成员函数) | | maintain | 在改变节点位置后，将节点的子树更新(私有成员函数) | | rotate | 将节点上移一个位置(公开成员函数) | | splay | 将节点旋转至根节点(公开成员函数) | | **查找** | | | get | 判断节点是父亲的左儿子或右儿子。 | | rk | 查询节点的排名 (公开成员函数) | | kth | 查询排名的值 (公开成员函数) | | pre | 查询前驱 (公开成员函数) | | nxt | 查询后继 (公开成员函数) | ## 可能的实现 ```cpp template < typename Key > struct Splay { int rt, tot, fa[MAXN], ch[MAXN][2], cnt[MAXN], sz[MAXN]; Key val[MAXN]; void maintain( int x ) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } bool get( int x ) { return x == ch[fa[x]][1]; } void clear( int x ) { ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0; } void rotate( int x ) { int y = fa[x], z = fa[y], chk = get( x ); ch[y][chk] = ch[x][chk ^ 1]; fa[ch[x][chk ^ 1]] = y; ch[x][chk ^ 1] = y; fa[y] = x; fa[x] = z; if ( z ) ch[z][y == ch[z][1]] = x; maintain( x ); maintain( y ); } void splay( int x ) { for ( int f = fa[x]; f = fa[x], f; rotate( x ) ) if ( fa[f] ) rotate( get( x ) == get( f ) ? f : x ); rt = x; } void ins( int k ) { if ( !rt ) { val[++tot] = k; cnt[tot]++; rt = tot; maintain( rt ); return; } int cnr = rt, f = 0; while ( true ) { if ( val[cnr] == k ) { cnt[cnr]++; maintain( cnr ); maintain( f ); splay( cnr ); break; } f = cnr; cnr = ch[cnr][val[cnr] < k]; if ( !cnr ) { val[++tot] = k; cnt[tot]++; fa[tot] = f; ch[f][val[f] < k] = tot; maintain( tot ); maintain( f ); splay( tot ); break; } } } int rk( int k ) { int res = 0, cnr = rt; while ( 1 ) { if ( k < val[cnr] ) { cnr = ch[cnr][0]; } else { res += sz[ch[cnr][0]]; if ( k == val[cnr] ) { splay( cnr ); return res + 1; } res += cnt[cnr]; cnr = ch[cnr][1]; } } } int kth( int k ) { int cnr = rt; while ( 1 ) { if ( ch[cnr][0] && k <= sz[ch[cnr][0]] ) { cnr = ch[cnr][0]; } else { k -= cnt[cnr] + sz[ch[cnr][0]]; if ( k <= 0 ) return val[cnr]; cnr = ch[cnr][1]; } } } int pre() { int cnr = ch[rt][0]; while ( ch[cnr][1] ) cnr = ch[cnr][1]; return cnr; } int nxt() { int cnr = ch[rt][1]; while ( ch[cnr][0] ) cnr = ch[cnr][0]; return cnr; } void del( int k ) { rk( k ); if ( cnt[rt] > 1 ) { cnt[rt]--; maintain( rt ); return; } if ( !ch[rt][0] && !ch[rt][1] ) { clear( rt ); rt = 0; return; } if ( !ch[rt][0] ) { int cnr = rt; rt = ch[rt][1]; fa[rt] = 0; clear( cnr ); return; } if ( !ch[rt][1] ) { int cnr = rt; rt = ch[rt][0]; fa[rt] = 0; clear( cnr ); return; } int x = pre(), cnr = rt; splay( x ); fa[ch[cnr][1]] = x; ch[x][1] = ch[cnr][1]; clear( cnr ); maintain( rt ); } int pre( int x ) { int ans; ins( x ); ans = val[pre()]; del( x ); return ans; } int nxt( int x ) { int ans; ins( x ); ans = val[nxt()]; del( x ); return ans; } bool empty() { return tot == 0; } int size() { return tot; } }; ``` <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/530.html">https://www.starroad.top/archives/530.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：December 14th, 2019 at 10:59 am © 允许规范转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
