个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
29
4
目录
- 「学习笔记」平衡树基础：Splay 和 Treap
- 知识点
- 平衡树概述
- Splay
- 旋转操作
- Splay 操作
- 插入 \(x\)
- 查询排名为 \(k\) 的数
- 查询 \(x\) 的排名
- 查询 \(x\) 的前驱
- 查询 \(x\) 的后继
- 删除 \(x\)
- 代码
- 替罪羊树
- Treap
- FHQ_Treap
- 树套树
- 平衡树的区间操作
- 例题
- P3391 文艺平衡树
- 思路
- P4036 [JSOI2008]火星人
- 思路
- P4309 [TJOI2013]最长上升子序列
- 思路
- 星系探索
- 思路
- 代码
二叉搜索树（BST）的简单定义:
这样的数据结构可以维护一个集合的以下操作:
该数据结构最优情况下单次查询仅需 \(\Theta(\log_2{n})\) 的时间复杂度，但通过构造输入可以使二叉搜索树退化为链，达到 \(\Theta(n)\) 的时间复杂度.
所以我们要让这棵二叉搜索树尽量平衡（深度接近 \(\log_2{n}\) ）.
于是就诞生了平衡树.
可以发现左旋/右旋后树的形态发生变化，但仍然满足二叉搜索树的性质.
Splay 的核心操作，即 把一个点提到根 .
分三种情况:
为什么要这么转呢？因为直接单旋上去无法保证复杂度， 随随便便就能卡掉 ，而双旋的时间复杂度可以用 势能分析法进行分析 .
根据 BST 的性质找到一个地方插入新点，然后把它旋上去.
假设当前到了点 \(p\) :
找到 \(x\) 提到根，左子树的大小加 \(1\) 就是答案.
把 \(x\) 提到根后，在左子树里一路往右走.
把 \(x\) 提到根后，在右子树里一路往左走.
最麻烦的一个.
首先我们把 \(x\) 提到根 。
const ll N = 2e5 + 10, INF = 1ll << 40;
namespace Splay {
class TreePoint {
public:
ll val, cnt, sz;
ll fa, son[2];
inline void New (ll num) { val = num, cnt = sz = 1, fa = son[0] = son[1] = 0; return; }
inline void Clear () { val = cnt = sz = fa = son[0] = son[1] = 0; return; }
};
class splay {
public:
TreePoint tr[N];
ll tot = 0, rt = 0;
#define va(p) tr[p].val
#define cn(p) tr[p].cnt
#define sz(p) tr[p].sz
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].son[lr]
inline void PushUp (ll p) { sz (p) = sz (so (p, 0)) + sz (so (p, 1)) + cn (p); return; } // Update the size.
inline bool Get (ll p) { return p == so (fa (p), 1); } // Left son(0) or right son(1)?
inline ll NewPoint (ll num) { tr[++tot].New (num); return tot; } // Build a new Point.
inline void Rotate (ll p) {
ll q = fa (p), r = fa (q), sd = Get (p);
so (q, sd) = so (p, sd ^ 1);
if (so (p, sd ^ 1)) fa (so (p, sd ^ 1)) = q;
so (p, sd ^ 1) = q, fa (q) = p, fa (p) = r;
if (r) so (r, q == so (r, 1)) = p;
PushUp (q), PushUp (p);
return;
} // Zig or zag.
inline void Splay (ll p) {
for (ll q = fa (p); q = fa (p), q; Rotate (p))
if (fa (q)) Rotate (Get (p) == Get (q) ? q : p);
rt = p;
return;
} // Splay's core operations!
inline void Out () {
_for (i, 1, tot) {
printf ("%lld : val=%lld cnt=%lld sz=%lld fa=%lld %lld %lld\n", i, va (i), cn (i), sz (i), fa (i), so (i, 0), so (i, 1));
}
puts ("");
return;
} // For debug.
inline void Insert (ll x) {
if (!rt) rt = NewPoint (x), PushUp (rt);
else {
ll p = rt;
while (1) {
ll sd = (bool)(va (p) < x);
if (va (p) == x) {
++cn (p);
PushUp (p), PushUp (fa (p));
break;
}
else if (so (p, sd)) p = so (p, sd);
else {
so (p, sd) = NewPoint (x);
fa (so (p, sd)) = p, p = so (p, sd);
PushUp (p), PushUp (fa (p));
break;
}
}
Splay (p);
}
return;
} // Insert a number x.
inline ll GetRank (ll x) {
ll p = rt, cnt = 1;
while (p) {
if (va (p) <= x) {
cnt += sz (so (p, 0));
if (va (p) == x) break;
cnt += cn (p);
p = so (p, 1);
}
else p = so (p, 0);
}
Splay (p);
return cnt;
} // Get x's rank.
inline ll GetKth (ll x) {
ll p = rt;
while (p) {
if (sz (so (p, 0)) < x) {
x -= sz (so (p, 0));
if (cn (p) >= x) break;
x -= cn (p);
p = so (p, 1);
}
else p = so (p, 0);
}
Splay (p);
return va (p);
} // Get k-th number.
inline ll RealPre () {
ll p = so (rt, 0);
if (p) {
while (so (p, 1)) p = so (p, 1);
Splay (p);
}
return p;
}
inline void Delete (ll x) {
GetRank (x);
ll sd = (bool)(so (rt, 1));
if (cn (rt) > 1) --cn (rt), PushUp (rt);
else if (!so (rt, 0) && !so (rt, 1)) tr[rt].Clear (), rt = 0;
else if (so (rt, 0) && so (rt, 1)) {
ll p = rt, q = RealPre ();
fa (so (p, 1)) = q;
so (q, 1) = so (p, 1);
tr[p].Clear ();
PushUp (rt);
}
else {
ll q = so (rt, sd);
tr[rt].Clear ();
fa (rt = q) = 0;
}
return;
} // Delete a number x.
inline ll Pre (ll x) {
Insert (x);
ll ans = va (RealPre ());
Delete (x);
return ans;
} // Get x's pre.
inline ll Next (ll x) {
Insert (x);
ll p = so (rt, 1), ans = 0;
if (p) {
while (so (p, 0)) p = so (p, 0);
Splay (p);
}
ans = va (rt);
Delete (x);
return ans;
} // Get x's next.
#undef va
#undef cn
#undef sz
#undef fa
#undef so
};
}
很暴力的一个东西.
定义一个平衡因子 \(\alpha\) （最好选 \(0.7\sim0.8\) ），插入/删除一个节点的时候检查是否存在一个节点的子树的大小乘上 \(\alpha\) 小于左/右儿子树的大小，如果有则把这棵子树直接拍平重构.
其他操作和普通 BST 一样.
namespace ScapeGoatTree {
const ldb alpha = 0.75;
const ll N = 1e5 + 10;
class TreePoint {
public:
ll val, cnt, sz, cp, del;
ll fa, son[2];
};
class SGT {
private:
ll tot = 0, rt = 0, dp[N], cd = 0;
TreePoint tr[N];
vec tmp, c;
#define va(p) tr[p].val
#define cn(p) tr[p].cnt
#define sz(p) tr[p].sz
#define de(p) tr[p].del
#define cp(p) tr[p].cp
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].son[lr]
inline ll NewP (ll num) {
ll p = cd ? dp[cd--] : ++tot;
va (p) = num;
cn (p) = sz (p) = 1;
cp (p) = fa (p) = so (p, 0) = so (p, 1) = de (p) = 0;
return p;
}
inline void DelP (ll p) {
va (p) = cn (p) = sz (p) = cp (p) = fa (p) = so (p, 0) = so (p, 1) = de (p) = 0;
dp[++cd] = p;
return;
}
inline void PushUp (ll p) {
sz (p) = (de (p) ? 0 : cn (p)) + sz (so (p, 0)) + sz (so (p, 1));
cp (p) = 1 + cp (so (p, 0)) + cp (so (p, 1));
return;
}
public:
inline void Clap (ll p) {
if (so (p, 0)) Clap (so (p, 0));
if (!de (p)) tmp.push_back (va (p)), c.push_back (cn (p));
if (so (p, 1)) Clap (so (p, 1));
DelP (p);
return;
}
inline ll PullUp (ll l, ll r, ll fat) {
if (l > r) return 0;
bdmd;
ll p = NewP (tmp[mid]);
cn (p) = c[mid], fa (p) = fat;
if (l < mid) so (p, 0) = PullUp (l, mid - 1, p);
if (mid < r) so (p, 1) = PullUp (mid + 1, r, p);
PushUp (p);
return p;
}
inline void ReBuild (ll p) {
ll q = fa (p);
tmp.clear (), c.clear ();
Clap (p);
if (!q) rt = PullUp (0, tmp.size () - 1, q);
else so (q, p == so (q, 1)) = PullUp (0, tmp.size () - 1, q);
return;
}
inline bool Bad (ll p) {
return cp (so (p, 0)) > cp (p) * alpha || cp (so (p, 1)) > cp (p) * alpha;
}
inline void Check (ll p) {
ll q = 0;
while (p) {
if (Bad (p)) q = p;
rt = p;
PushUp (p);
p = fa (p);
}
if (q) ReBuild (q);
return;
}
inline void Insert (ll num) {
ll p = rt;
if (!rt) {
rt = NewP (num);
return;
}
while (1) {
if (va (p) == num) {
++cn (p);
if (de (p)) de (p) = 0;
Check (p);
return;
}
ll sd = num > va (p);
if (so (p, sd)) p = so (p, sd);
else {
so (p, sd) = NewP (num);
fa (so (p, sd)) = p;
Check (p);
return;
}
}
return;
}
inline void Delete (ll num) {
ll p = rt;
while (p) {
if (va (p) == num) {
--cn (p);
if (cn (p) < 1) {
cn (p) = 0;
de (p) = 1;
}
Check (p);
return;
}
ll sd = num > va (p);
p = so (p, sd);
}
return;
}
inline ll GetRank (ll num) {
ll p = rt, rk = 1;
while (p) {
if (va (p) > num) {
p = so (p, 0);
continue;
}
rk += sz (so (p, 0));
if (num == va (p)) break;
rk += cn (p);
p = so (p, 1);
}
return rk;
}
inline ll GetKth (ll k) {
ll p = rt;
while (p) {
if (sz (so (p, 0)) >= k) {
p = so (p, 0);
continue;
}
k -= sz (so (p, 0));
if (k <= cn (p)) break;
k -= cn (p);
p = so (p, 1);
}
return va (p);
}
inline ll Pre (ll num) { return GetKth (GetRank (num) - 1); }
inline ll Nxt (ll num) { return GetKth (GetRank (num + 1)); }
#undef va
#undef cn
#undef sz
#undef de
#undef cp
#undef fa
#undef so
};
}
每个节点还要存一个随机权值，使得整棵树不仅对于原权值来说是一棵 BST，对于随机权值来说还是一个堆，在随机状态下一棵 Treap 是比较 \(\log_2n\) 层的。 当然不排除你脸太黑导致 Treap 退化成链的极小可能.
那么插入的时候，如果新节点不满足堆的性质了，需要往上旋转。删除的时候直接旋到叶子结点删掉，或者只剩一个儿子的时候直接让儿子代替自己.
其他操作和普通 BST 一样.
namespace TREAP {
class TreePoint {
public:
ll val, rk, sz, cnt;
ll son[2];
inline void NewP (ll x) { val = x, rk = rand (), cnt = sz = 1, son[0] = son[1] = 0;return; }
};
class Treap {
public:
TreePoint tr[N];
ll tot = 0, rt = 0;
#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define cn(p) tr[p].cnt
#define so(p, lr) tr[p].son[lr]
inline void PushUp (ll p) { sz (p) = cn (p) + sz (so (p, 0)) + sz (so (p, 1)); return; }
inline ll NewP (ll num) { tr[++tot].NewP (num); return tot; }
inline void DelP (ll p) { va (p) = rk (p) = sz (p) = cn (p) = so (p, 0) = so (p, 1) = 0;return; }
inline void Rotate (ll& p, ll sd) {
ll q = so (p, sd ^ 1);
so (p, sd ^ 1) = so (q, sd);
so (q, sd) = p, p = q;
PushUp (so (q, sd)), PushUp (q);
return;
}
void Insert (ll& p, ll x) {
if (!p) {
p = NewP (x);
return;
}
if (va (p) == x) ++cn (p);
else {
bool sd = (va (p) < x);
Insert (so (p, sd), x);
if (rk (so (p, sd)) > rk (p)) Rotate (p, sd ^ 1);
}
PushUp (p);
return;
}
void Delete (ll& p, ll x) {
if (!p) return;
if (va (p) == x) {
if (cn (p) == 1) {
if (!so (p, 0) && !so (p, 1)) DelP (p), p = 0;
else if (!so (p, 0) || !so (p, 1)) p = so (p, 0) + so (p, 1);
else {
ll sd = (rk (so (p, 1)) < rk (so (p, 0)));
Rotate (p, sd), Delete (so (p, sd), x);
}
}
else --cn (p);
}
else Delete (so (p, (x > va (p))), x);
PushUp (p);
return;
}
ll GetRank (ll p, ll x) {
if (!p) return 1;
if (va (p) == x) return 1 + sz (so (p, 0));
if (va (p) < x) return GetRank (so (p, 1), x) + sz (so (p, 0)) + cn (p);
return GetRank (so (p, 0), x);
}
ll GetKth (ll p, ll x) {
if (!p) return 0;
if (x <= sz (so (p, 0))) return GetKth (so (p, 0), x);
x -= sz (so (p, 0));
if (x <= cn (p)) return va (p);
x -= cn (p);
return GetKth (so (p, 1), x);
}
ll Pre (ll x) { return GetKth (rt, GetRank (rt, x) - 1); }
ll Next (ll x) { return GetKth (rt, GetRank (rt, x + 1)); }
#undef va
#undef rk
#undef sz
#undef cn
#undef so
};
}
FHQ_Treap 依旧满足 Treap 的性质，但是操作方式很神奇！ 。
FHQ_Treap 也被称为无旋 Treap，因为它的所有操作都没有恶心的旋转，只有分裂和合并两个基础操作！ 。
分裂有两种方法：按权值裂和按排名裂。一般来说，只当平衡树的时候通常按权值裂，维护序列的时候按排名裂。具体怎么裂见代码和例题.
合并的时候要保证第一棵树的所有权值都比第二棵树小，注意合的过程中要保证 Treap 的性质.
为了方便写我没有写副本数.
然后就是六个操作了:
插入 。
按 \(x\) 裂成 \(a,b\) 两棵树，然后按 \(a,x,b\) 的顺序合起来 。
删除 。
这绝对是删除操作最简单的平衡树了！先按 \(x\) 裂成 \(a,b\) 两棵树，再把 \(a\) 按 \(x-1\) 裂成 \(a,c\) 两棵树，此时 。
查询排名为 \(k\) 的数 。
和普通 BST 一样.
查询 \(x\) 的排名 。
按 \(x-1\) 裂成 \(a,b\) 两棵树， \(a\) 的大小加一就是答案 。
查询 \(x\) 的前驱 。
按 \(x-1\) 裂成 \(a,b\) 两棵树， \(a\) 里的最大值 。
查询 \(x\) 的后继 。
按 \(x-1\) 裂成 \(a,b\) 两棵树， \(b\) 里的最小值 。
namespace FHQ_TREAP {
class TreeNode {
public:
ll val, rk, sz, son[2];
inline void Add (ll num) { val = num, rk = rand (), sz = 1, son[0] = son[1] = 0; return; }
};
class FHQTreap {
private:
TreeNode tr[N];
ll tot = 0, rt = 0, a, b, c;
#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define so(p, lr) tr[p].son[lr]
inline ll NewP (ll num) { tr[++tot].Add (num); return tot; }
inline void PushUp (ll p) { sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1)); return; }
void Split (ll p, ll x, ll& l, ll& r) {
if (!p) l = r = 0;
else {
if (va (p) <= x) l = p, Split (so (p, 1), x, so (p, 1), r);
else r = p, Split (so (p, 0), x, l, so (p, 0));
PushUp (p);
}
return;
}
inline ll Merge (ll l, ll r) {
if (!l || !r) return l + r;
if (rk (l) < rk (r)) {
so (l, 1) = Merge (so (l, 1), r);
PushUp (l);
return l;
}
else {
so (r, 0) = Merge (l, so (r, 0));
PushUp (r);
return r;
}
}
public:
inline void Insert (ll x) {
Split (rt, x, a, b);
rt = Merge (Merge (a, NewP (x)), b);
return;
}
inline void Delete (ll x) {
Split (rt, x, a, b);
Split (a, x - 1, a, c);
rt = Merge (Merge (a, Merge (so (c, 0), so (c, 1))), b);
return;
}
inline ll GetRank (ll x) {
Split (rt, x - 1, a, b);
ll ans = sz (a) + 1;
rt = Merge (a, b);
return ans;
}
inline ll GetKth (ll x) {
ll p = rt;
while (p) {
if (x <= sz (so (p, 0))) p = so (p, 0);
else {
x -= sz (so (p, 0)) + 1;
if (!x) break;
p = so (p, 1);
}
}
return va (p);
}
inline ll Pre (ll x) {
Split (rt, x - 1, a, b);
ll p = a;
while (so (p, 1)) p = so (p, 1);
rt = Merge (a, b);
return va (p);
}
inline ll Next (ll x) {
Split (rt, x, a, b);
ll p = b;
while (so (p, 0)) p = so (p, 0);
rt = Merge (a, b);
return va (p);
}
#undef va
#undef rk
#undef sz
#undef so
};
}
用于维护单点修改和区间第 \(k\) 大，排名，前驱和后继的查询.
首先建立一棵线段树，每个节点单建一棵平衡树维护这个区间（线段树的每一层有 \(n\) 个节点，一共 \(\log_2n\) 层，因此只有 \(n\log_2n\) 个节点，不会 TLE/MLE）.
然后是如何维护五个操作:
const ll N = 1e5 + 10, inf = 2147483647;
namespace FHQ_TREAP {
class TreeNode {
public:
ll val, rk, sz, son[2];
inline void Add (ll num) noexcept { val = num, rk = rand (), sz = 1, son[0] = son[1] = 0; return; }
} tr[N << 4];
ll tot = 0, len = 0, free[N << 4];
#define va(p) tr[p].val
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define so(p, lr) tr[p].son[lr]
class FHQTreap {
private:
ll rt = 0, a, b, c;
inline void PushUp (ll p) noexcept { sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1)); }
inline ll NewP (ll num) noexcept {
ll p = len ? free[len--] : ++tot;
tr[p].Add (num);
return p;
}
inline void DelP (ll p) noexcept {
va (p) = rk (p) = sz (p) = so (p, 0) = so (p, 1) = 0;
free[++len] = p;
return;
}
inline void Split (ll p, ll x, ll& l, ll& r) noexcept {
if (!p) l = r = 0;
else {
if (va (p) <= x) l = p, Split (so (p, 1), x, so (p, 1), r);
else r = p, Split (so (p, 0), x, l, so (p, 0));
PushUp (p);
}
return;
}
inline ll Merge (ll l, ll r) noexcept {
if (!l || !r) return l + r;
if (rk (l) > rk (r)) {
so (l, 1) = Merge (so (l, 1), r);
PushUp (l);
return l;
}
else {
so (r, 0) = Merge (l, so (r, 0));
PushUp (r);
return r;
}
}
public:
inline void Insert (ll x) noexcept {
Split (rt, x, a, b);
rt = Merge (Merge (a, NewP (x)), b);
return;
}
inline void Delete (ll x) noexcept {
Split (rt, x, a, b);
Split (a, x - 1, a, c);
rt = Merge (Merge (a, Merge (so (c, 0), so (c, 1))), b);
DelP (c);
return;
}
inline ll GetRank (ll x) noexcept {
Split (rt, x - 1, a, b);
ll ans = sz (a);
rt = Merge (a, b);
return ans;
}
inline ll Pre (ll x) noexcept {
Split (rt, x - 1, a, b);
ll p = a;
while (so (p, 1)) p = so (p, 1);
rt = Merge (a, b);
return va (p);
}
inline ll Next (ll x) noexcept {
Split (rt, x, a, b);
ll p = b;
while (so (p, 0)) p = so (p, 0);
rt = Merge (a, b);
return va (p);
}
};
#undef va
#undef rk
#undef sz
#undef so
}
namespace SEGMENT_TREE {
class SegmentTree {
private:
FHQ_TREAP::FHQTreap tr[N << 2];
#define ls(p) p << 1, l, mid
#define rs(p) p << 1 | 1, mid + 1, r
public:
inline void Build (ll p, ll l, ll r, ll* a) noexcept {
if (l != r) {
ll mid = md;
Build (ls (p), a);
Build (rs (p), a);
}
tr[p].Insert (inf), tr[p].Insert (-inf);
_for (i, l, r) tr[p].Insert (a[i]);
return;
}
inline void Update (ll p, ll l, ll r, ll x, ll y, ll z) noexcept {
if (r < x || x < l) return;
if (l != r) {
ll mid = md;
Update (ls (p), x, y, z);
Update (rs (p), x, y, z);
}
tr[p].Delete (z), tr[p].Insert (y);
}
inline ll QueryRank (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
if (ri < l || r < le) return 0;
ll mid = md;
if (le <= l && r <= ri) return tr[p].GetRank (x) - 1;
else return QueryRank (ls (p), le, ri, x) + QueryRank (rs (p), le, ri, x);
}
inline ll QueryKth (ll le, ll ri, ll x, ll n, ll mx) noexcept {
ll l = 0, r = mx, ans = 0;
while (l <= r) {
ll mid = md;
if (QueryRank (1, 1, n, le, ri, mid) + 1 <= x) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans;
}
inline ll QueryPre (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
if (ri < l || r < le) return -inf;
ll mid = md;
if (le <= l && r <= ri) return tr[p].Pre (x);
else return std::max (QueryPre (ls (p), le, ri, x), QueryPre (rs (p), le, ri, x));
}
inline ll QueryNext (ll p, ll l, ll r, ll le, ll ri, ll x) noexcept {
if (ri < l || r < le) return inf;
ll mid = md;
if (le <= l && r <= ri) return tr[p].Next (x);
else return std::min (QueryNext (ls (p), le, ri, x), QueryNext (rs (p), le, ri, x));
}
};
}
平衡树不是只能平衡树，也可以进行区间操作.
用平衡树中序遍历顺序不变的性质，维护序列中每个数的前后位置（即把按数值排序变为按下标排序）.
操作时，把需要操作/查询的区间放在一颗子树上再直接对子树进行操作/查询.
如果操作对子树的所有点生效，应该给子树打个标记，旋转/分裂/合并的时候随手下传标记.
使用 Splay：通过对 \(l-1\) 和 \(r+1\) 提根使得区间 \([l, r]\) 在一颗子树上，然后对这棵子树进行操作.
使用 FHQ-Treap：把区间 \([l, r]\) 裂出来，然后对这棵子树进行操作，再合并回去.
平衡树还支持插入/删除一个点，所以维护序列的时候还可以在任意位置加入/删除一个数.
另外，FHQ-Treap 裂开合并的神奇操作还支持对一个区间进行移动.
对需要操作的区间打个翻转标记，同时交换其左右儿子.
维护一棵子树的字符串的哈希值，然后就是裸的区间操作了.
不难发现每次插入的数都会比之前插入的数都大，因此插完之后最长上升子序列的长度不会变化.
那么每个节点维护一个子树最长上升子序列的长度的最大值，插入时选一个前面的最长的最长上升子序列接上.
把这棵树转换成 dfs 序序列，然后对于三个操作:
const ll N = 1e6+ 10;
namespace FHQ_TREAP {
class TreeNode {
public:
ll val, pn, rk, sz, so[2], ta, sum, sp, fa;
inline void Add (ll num, ll tmp) { sum = val = num * tmp, sp = pn = tmp, rk = rand (), sz = 1, so[0] = so[1] = 0; return; }
};
class FHQTreap {
private:
TreeNode tr[N];
ll tot = 0, rt = 0, a, b, c;
#define va(p) tr[p].val
#define ta(p) tr[p].ta
#define rk(p) tr[p].rk
#define sz(p) tr[p].sz
#define pn(p) tr[p].pn
#define su(p) tr[p].sum
#define sp(p) tr[p].sp
#define fa(p) tr[p].fa
#define so(p, lr) tr[p].so[lr]
inline ll NewP (ll num, ll pn) { tr[++tot].Add (num, pn); return tot; }
inline void PushUp (ll p) {
sz (p) = 1 + sz (so (p, 0)) + sz (so (p, 1));
su (p) = va (p) + su (so (p, 0)) + su (so (p, 1));
sp (p) = pn (p) + sp (so (p, 0)) + sp (so (p, 1));
fa (so (p, 0)) = fa (so (p, 1)) = p;
return;
}
inline void Tag (ll p, ll num) {
ta (p) += num;
va (p) += num * pn (p);
su (p) += num * sp (p);
return;
}
inline void PushDown (ll p) {
if (!ta (p)) return;
if (so (p, 0)) Tag (so (p, 0), ta (p));
if (so (p, 1)) Tag (so (p, 1), ta (p));
fa (so (p, 0)) = fa (so (p, 1)) = p;
ta (p) = 0;
return;
}
inline void Split (ll p, ll x, ll& l, ll& r) {
if (!p) l = r = 0;
else {
PushDown (p);
if (sz (so (p, 0)) < x) l = p, Split (so (p, 1), x - sz (so (p, 0)) - 1, so (p, 1), r);
else r = p, Split (so (p, 0), x, l, so (p, 0));
PushUp (p);
}
return;
}
inline ll Merge (ll l, ll r) {
PushDown (l), PushDown (r);
if (!l || !r) return l + r;
if (rk (l) > rk (r)) {
so (l, 1) = Merge (so (l, 1), r);
PushUp (l);
return l;
}
else {
so (r, 0) = Merge (l, so (r, 0));
PushUp (r);
return r;
}
}
inline ll GetRank (ll x) {
ll cnt = sz (so (x, 0)) + 1;
for (ll p = x; fa (p); p = fa (p))
if (so (fa (p), 1) == p) cnt += sz (so (fa (p), 0)) + 1;
return cnt;
}
public:
inline void Insert (ll x, ll p) {
rt = Merge (rt, NewP (x, p));
return;
}
inline void Modify (ll l, ll r, ll x) {
l = GetRank (l), r = GetRank (r);
Split (rt, r, a, b);
Split (a, l - 1, a, c);
Tag (c, x);
rt = Merge (Merge (a, c), b);
return;
}
inline void Move (ll l, ll r, ll x) {
l = GetRank (l), r = GetRank (r), x = GetRank (x);
if (x > r) x -= r - l + 1;
Split (rt, r, a, b);
Split (a, l - 1, a, c);
a = Merge (a, b);
Split (a, x, a, b);
rt = Merge (Merge (a, c), b);
return;
}
inline ll Query (ll x) {
x = GetRank (x);
Split (rt, x, a, b);
ll ans = su (a);
rt = Merge (a, b);
return ans;
}
#undef va
#undef ta
#undef rk
#undef sz
#undef pn
#undef su
#undef sp
#undef fa
#undef so
};
}
namespace SOLVE {
FHQ_TREAP::FHQTreap tr;
ll n, m, fa[N], w[N], cnt;
ll dfn[N], sec[N][2];
std::vector<ll> tu[N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline char rch () {
char c = getchar ();
while (c < 'A' || 'Z' < c) c = getchar ();
return c;
}
inline void Dfs (ll x) {
dfn[sec[x][0] = ++cnt] = x;
tr.Insert (w[x], 1);
far (i, tu[x]) Dfs (i);
sec[x][1] = ++cnt;
tr.Insert (w[x], -1);
return;
}
inline void In () {
n = rnt ();
_for (i, 2, n) {
fa[i] = rnt ();
tu[fa[i]].push_back (i);
}
_for (i, 1, n) w[i] = rnt ();
m = rnt ();
Dfs (1);
return;
}
inline void Out () {
while (m--) {
char opt = rch ();
if (opt == 'Q') {
ll d = rnt ();
printf ("%lld\n", tr.Query (sec[d][0]));
}
else if (opt == 'C') {
ll x = rnt (), y = rnt ();
tr.Move (sec[x][0], sec[x][1], sec[y][0]);
}
else {
ll x = rnt (), y = rnt ();
tr.Modify (sec[x][0], sec[x][1], y);
}
}
return;
}
}
最后此篇关于「学习笔记」平衡树基础：Splay和Treap的文章就讲到这里了,如果你想了解更多关于「学习笔记」平衡树基础：Splay和Treap的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
29
4
0
我正在尝试了解二叉树的属性。但我不确定一件事: 定义。二叉树的声明: 如果对于每个节点，它认为左子树中的内部节点数和右子树中的内部节点数最多相差 1，则二叉树是平衡的。 如果任意两个叶子的差异都存在，
我有一个带有分片键和索引的集合。但是当我运行平衡时，不会为这个集合移动 block ，因为其他集合 block 正在按预期移动到其他机器。此集合中仅移动了一个 block 。 最佳答案 目前(这将在不
给定一个data.table如下，id1是一个subject-level ID，id2是一个within-subject repeated-measure ID，X 是数据变量，其中有很多。我想平衡数
由于 C++ 集合是在二叉树中实现的，如果我们以递增或递减顺序插入项目，那么集合将更像是一个列表而不是树。有没有什么方法可以在插入项目后平衡树？ 最佳答案 C++ 集(即 std::set)通常实现为
我是一名初学者程序员，设计了一个智能手机网站，我有一个主体背景图像，我想慢慢改变颜色平衡，交替颜色，就像有人将 Photoshop 颜色平衡控制条调整一定百分比一样。任一方向。当您查看页面时，这种情况
我开发了一段多线程代码。该代码在 Web 应用程序中调用，因此可能由多个线程(请求)并行调用。为了控制此代码将要创建的线程数量(通过多个并行请求调用)，我使用静态共享 ThreadPoolExecut
我正在为 Linux 内核开发一些网络驱动程序。我有几个 if-else 条件，我正在重新分配或释放“skb”结构——这是我有点困惑的地方。关于我在那些 if-else 中做什么 - 我遇到了 2 种
平衡 BST 的最佳和最差搜索性能是什么？每种情况发生时如何用一句话解释？ 最佳答案 最佳情况:当搜索到的元素位于树的根部时。你得到 O(1)。 最坏情况:当搜索元素在最长分支的叶子处时，树是单边的。
我在平衡 AVL 树问题上遇到了麻烦，因为我的解决方案似乎与教科书后面的解决方案冲突。我查看了 AVL 树的在线可视化，他们认为我的是正确的。我的课本错了吗？ 这是树: 然后我必须将 65 插入到这个
我有一个系统，我在其中使用 RS232 来控制一个灯，该灯接受以浮点形式给出的表示电压(在 2.5 - 7.5 范围内)的输入。然后控件会给出 0 到 6000 范围内的输出，这是传感器拾取的亮度。
我有一个分层目录，每个目录中有很多文件，每个文本文件中有很多 URL 字符串。我想下载 Hadoop 中所有文件中的所有 URL，以实现更好的平衡。 例如，如果我有 1+5 个节点的 Hadoop 集
请查看附件图片，这是一种跷跷板。但从图像来看，黑体具有相同的密度。并且水平矩形使用“Revolute”关节与三角形相连。但仍然没有任何建议。在目前的情况下，它需要平衡。 最佳答案 由于浮点精度等限制导
因此，在平衡 KD 树时，您应该找到中位数，然后将所有较小的元素放在左子树上，将较大的元素放在右子树上。但是，如果您有多个元素与中位数具有相同的值，会发生什么情况？他们进入左子树，右子树还是丢弃它们？
请帮我找到一种干净的方法来从现有数组中创建一个新数组。如果任何类的示例数小于该类中的最大示例数，则应该进行过采样。样本应该从原始数组中提取(随机或顺序都没有区别) 比方说，初始数组是这样的: [ 2
我是一名软件开发人员，但想成为服务器可扩展性领域的新架构师。 在多个服务使用同一数据集的情况下，旨在扩展冗余和负载平衡。 问题是:在一个理想主义的系统中，服务是否应该尝试优化它们的内部处理以减少对远程
假设我有 10 个分区用于 Kafka 中的给定主题。 我的选择是在消费者之间自动平衡这 10 个分区的负载？ 我已经阅读了这篇文章 https://stackoverflow.com/a/28580
假设我有一个 B 树，其节点为 3-4 配置(3 个元素和 4 个指针)。假设我按照规则合法地建立我的树，我是否有可能达到一层中有两个节点并且一个节点有 4 个退出指针而另一个节点只有两个退出指针的情
当光标在一个括号上时，如何跳转到配对括号。很高兴在 工作emacs -nw . 就像 % 在 Vim 中。 ;;从@Lindy、@Francesco 得到提示后，我发现了更多: C-M-f
我在平衡 AVL 树时遇到问题。我一直在寻找如何平衡它们的步骤，但我找不到任何有用的东西。 我知道有4种: 单左旋 单右旋 双左右旋转 双左右旋转 但我就是无法得到如何选择其中之一和 在哪个节点上应用
我想获得类似于打印中平衡文本行但用于 block 元素的结果。假设在一个 300/100 像素的容器中有一组 50/50 像素的盒子。在容器中 float 盒子将使它们填满一“行”，然后像这样包裹到下
我是一名优秀的程序员,十分优秀！