博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
左偏树 / 非旋转treap学习笔记
阅读量:4840 次
发布时间:2019-06-11

本文共 5826 字,大约阅读时间需要 19 分钟。

背景

非旋转treap真的好久没有用过了... 左偏树由于之前学的时候没有写学习笔记, 学得也并不牢固. 所以打算写这么一篇学习笔记, 讲讲左偏树和非旋转treap.

左偏树

定义

  • 左偏树(Leftist Tree)是一种可并堆(Mergeable Heap), 它除了支持优先队列的三个基本操作(插入,删除,取最小节点), 还支持一个很特殊的操作——合并操作;
  • 左偏树是一棵堆有序(Heap Ordered)二叉树;
  • 左偏树满足左偏性质(Leftist Property):
    • 节点的键值小于或等于它的左右子节点的键值;
    • 节点的左子节点的距离不小于右子节点的距离;
    • 节点的左子节点右子节点也是一颗左偏树.

操作

注: 这里的左偏树默认是大根堆.

合并

合并两棵左偏树. 在合并操作中, 假设这两棵treap的根节点分别为uv.

  • 比较这两个根节点的权值, 大的作为当前节点,
  • 合并当前节点的右儿子和另一个根节点.
  • 比较当前节点的两个儿子, 假如右儿子的距离大于左儿子, 则交换两个儿子节点.

插入

插入一个节点.

把这个节点当成是只有根节点的一棵左偏树, 用合并的方法合并至原树中即可.

时间复杂度及证明

我们发现, 对于一棵点数为\(n\)的左偏树, 其最右链的长度不超过\(\log n\)(这里的证明我不太会, 就稍微意会一下吧), 因此合并两棵大小为\(n\)的左偏树的时间复杂度为\(O(\log n)\). 我们考虑开始时每棵左偏树都只有一个节点, 则从初始状态合并至所有节点都在一棵树上的时间复杂度为\[O\left(\frac{n}{2^1} \log 2^0 + \frac{n}{2^2} \log 2^1 + \frac{n}{2^3} \log 2^2 + ... + \frac{n}{2^{k + 1}} \log 2^k \right) = O\left(\frac{n}{2} \log n\right) = O(n \log n)\]

代码

直接看Monkey King的代码就可以了吧.

#include 
#include
#include
#include
#include
const int N = (int)1e5;namespace Zeonfai{ inline int getInt() { int a = 0, sgn = 1; char c; while(! isdigit(c = getchar())) if(c == '-') sgn *= -1; else if(c == EOF) exit(0); while(isdigit(c)) a = a * 10 + c - '0', c = getchar(); return a * sgn; } void _print(int a) { if(! a) return; _print(a / 10); putchar('0' + a % 10); } inline void println(int a) { if(a < 0) putchar('-'), a *= -a; if(! a) putchar(0); _print(a); putchar('\n'); }}struct disjointSet{ int anc[N + 1]; inline void initialize() { memset(anc, -1, sizeof(anc)); } int access(int u) { return ~ anc[u] ? anc[u] = access(anc[u]) : u; } void link(int u, int pre) { anc[u] = pre; }}st;struct leftistTrees{ struct node { int suc[2], dis, w; }nd[N + 1]; inline void newNode(int u, int w) { nd[u].w = w, nd[u].dis = 0, nd[u].suc[0] = nd[u].suc[1] = -1; } inline void modify(int u) { newNode(u, nd[u].w >> 1); } inline int merge(int pre, int u, int v) { if(! (~ u)) { if(~ v) st.link(v, pre); return v; } if(! (~ v)) { if(~ u) st.link(u, pre); return u; } if(nd[u].w < nd[v].w) std::swap(u, v); nd[u].suc[1] = merge(u, nd[u].suc[1], v); if(! (~ nd[u].suc[0]) || nd[nd[u].suc[1]].dis > nd[nd[u].suc[0]].dis) std::swap(nd[u].suc[0], nd[u].suc[1]); nd[u].dis = ~ nd[u].suc[1] ? nd[nd[u].suc[1]].dis + 1 : 0; st.link(u, pre); return u; } inline int pop(int u) { return merge(-1, nd[u].suc[0], nd[u].suc[1]); } inline int get(int u) { return nd[u].w; }}hp;int main(){ #ifndef ONLINE_JUDGE freopen("HDU1512.in", "r", stdin); freopen("HDU1512.out", "w", stdout); #endif using namespace Zeonfai; while(int n = getInt()) { for(int i = 1; i <= n; ++ i) hp.newNode(i, getInt()); int m = getInt(); st.initialize(); for(int i = 0; i < m; ++ i) { int u = getInt(), v = getInt(), rtU = st.access(u), rtV = st.access(v); if(rtU == rtV) { puts("-1"); continue; } int nwRtU = hp.pop(rtU), nwRtV = hp.pop(rtV); hp.modify(rtU), hp.modify(rtV); rtU = hp.merge(-1, nwRtU, rtU), rtV = hp.merge(-1, nwRtV, rtV); int rt = hp.merge(-1, rtU, rtV); println(hp.get(rt)); } }}

非旋转treap

定义

treap即是tree + heap. 不懂的可以先学习普通treap.

非旋转treap的特别之处在于, 它的操作不依赖于旋转, 而使用类似于左偏树的合并的方式来实现.

操作

首先是一些基本的操作:

合并

给定两棵treap的根节点, 将它们合并起来. 注意这里要求其中一棵treap的任意元素都比另一棵的任意元素小. 实现: 首先把优先级高的一个根节点作为当前节点, 假如另一棵treap比当前点小, 则将其与当前点的左儿子合并, 否则和右儿子合并. 是不是和左偏树的合并非常类似?

分裂

对于一棵以u为根的treap, 将其权值前\(k\)小与剩下部分切开成 两棵 treap并且将其根节点返回. 令sz为根节点节点的左子节点的大小分三种情况讨论:

  • \(sz = k\), 则直接断开左儿子, 返回左儿子和当前节点即可;
  • \(sz > k\), 同样地断开左儿子, 递归左子树, 得到的结果假设为\((first, second)\), 合并\(u\)\(second\)作为第二关键字返回即可.
  • \(sz < k\), 断开右儿子, 递归右子树, 得到的结果假设为\((first, second)\), 将\(u\)\(first\)合并作为第一关键字返回即可.

余下的操作都是基于以上的merge和split.

插入

直接merge上去即可.

删除 / 查询

假设要删除第\(L\)到第\(R\)个点, 则先split(R), 再对返回的\(first\)进行\(split(L)\)得到的second即是\([L, R]\)区间.

时间复杂度

显然的\(O(n \log n)\)

代码

只写了merge和split, 而且正确性无法保证.

#include 
#include
struct treap{ struct node { int w, fix, sz; node* suc[2]; }; node* rt; node* merge(node *u, node *v) { if(u == NULL) return v; if(v == NULL) return u; if(u->fix < v->fix) std::swap(u, v); u->suc[v->w > u->w] = merge(u->suc[v->w > u->w], v); return u; } std::pair
split(node *u, int k) { int tmp = u->suc[0] == NULL ? 0 : u->suc[0]->sz; if(tmp == k) { u->suc[0] = NULL; return std::make_pair(u->suc[0], u); } else if(tmp > k) { std::pair
res = split(u->suc[0], k); u->suc[0] = NULL; return std::make_pair(res.first(), merge(res.second, u)); } else if(tmp < k) { std::pair
res = split(u->suc[1], k - tmp - 1); u->suc[1] = NULL; return std::make_pair(merge(res.first, u), res.second); } }}int main(){ using namespace Zeonfai; int n = getInt(); for(int i = 0; i < n; ++ i) { int opt = getInt(); if(opt == 1) }}

就这样吧.

转载于:https://www.cnblogs.com/ZeonfaiHo/p/7103370.html

你可能感兴趣的文章
动态规划:HDU1712-ACboy needs your help(分组背包问题)
查看>>
PAT A1009 Product of Polynomials(25)
查看>>
libFFM 与 python-libffm 安装遇到的一系列问题-解决方案
查看>>
数据摘要pandas
查看>>
浅谈C语言中的位段
查看>>
2019.04.25 第七次训练 【2017-2018 ACM-ICPC Asia East Continent League Final (ECL-Final 2017)】...
查看>>
javascript正则表达式复习
查看>>
【JVM】类加载器及双亲委派机制实例解析
查看>>
python 生成 pyc 文件
查看>>
linux清除git账号密码
查看>>
grep awk 查看nginx日志中所有访问的ip并 去重
查看>>
vue 遇到防盗链 img显示不出来
查看>>
C# GDI graphics.DrawImage 的参数问题
查看>>
【WPF】2、美化控件
查看>>
css 光标
查看>>
深入理解await与async
查看>>
将一个数字扁平化,去重并升序
查看>>
边缘缓存模式(Cache-Aside Pattern)
查看>>
博文汇总
查看>>
在Java大环境下.NET程序员如何夺得一线生机
查看>>