平衡树全家桶 2
平衡树全家桶 2
笛卡尔树
仅支持静态，不支持动态
建树过程：单调栈。对于每个新加入的点
- 最后pop掉的点 ，则 是 左子树
- 最后pop不走的点 ，则 是 右子树
用于静态区间最大值之类的维护
Size Balanced Tree
树的性质：叔叔比侄子大，即：
1 | size(N.left) >= size(N.right.left) |
平衡维护：
-
右左过大：转两次它
-
右右过大：转一次右
-
左右过大：转两次它
-
左左过大：转一次左
AVL
保证左右子树高度差严格小于1
感觉旋转的那些东西还是大同小异。反正就是Rotate，已经不想写了
红黑树
红黑树有如下性质：
- 每个点要么红色、要么黑色
- 根到任何一个叶子节点经过的黑色点的数量相同
- 没有任何相邻的红色节点
- 根节点为黑色
我们考虑插入一个点，就先让它是红色，然后向上维护，保证没有出现连续的红色。而每次Rotate过程中也保证黑色之和不变
-
Flip：祖父的左右都是红色
-
祖父的另一边是黑色，但这边是顺着
-
如果这边是反的：我们可以先Rotate，转为上一种情况
左偏红黑树
在红黑树的基础上，保证只有左子树能是红色，右边必须是黑色
其主要优势是，分类讨论的情况很少，很适合手搓
这篇文章讲的不错：2-3树与红黑树 - riteme.site
-
常规flip：
-
连续左红：
-
碰到右红节点：
AA树
变成了右边可以是红色，左边必须是黑色
好像里面操作可能有一些不一样，但大同小异，不深究了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2026-07-07
平衡树全家桶 1
平衡树全家桶 1 Treap Treap = Tree（BST）+ Heap 左旋 右旋 这两个显然，推一推就行 我们对每个节点附一个随机权值，用于维护小根堆/大根堆 每次，先修改（按照二叉搜索树的方式），然后转转转，使其符合堆 FHQ-Treap 无旋Treap 同样有BST和Heap的性质。（只要是Treap，其随机权值就给了其深度为log的保证） 我们有两种操作： spilt(root, val) 按照val划分 如果当前点 <= val，则 split(R, val)，并把得到的其中一棵树连为根节点的新右子树 如果当前点 > val，则 split(L, v...
2023-09-15
笛卡尔树建树
笛卡尔树建树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906457 拿个单调队列维护 最后pop出来的就是它的左儿子 现在还在的，它是他的右儿子 1234567891011int build() { int S[N]; for(int i=1; i<=n; ++i) { while(top && T[S[top]].val < T[i].val) T[i].son[0]=S[top], -...
2023-10-18
set维护连续段+线段树：1018T2
set维护连续段+线段树：1018T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133914164 http://cplusoj.com/d/senior/p/386?tid=652f5fe6c1fe41bc229c18fb 线段树维护01，和，支持翻转操作 用类似珂朵莉树的方法维护连续段，连续段之间分别统计，取max 1234567891011121314151617181920212223242526272829303132333435363738...
2021-11-18
【P2344 [USACO11FEB]Generic Cow Protests G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574309.html 题目链接 首先朴素dp不用讲，设 dpidp_idpi 表示前 iii 个数划分的总方案数，SiS_iSi 表示前 iii 个数的和。 dpi=∑j=0i−1dpj (Si−Sj⩾0)dp_i=\sum_{j=0}^{i-1}dp_j\,\,\,(S_i-S_j\geqslant 0) dpi=j=0∑i−1dpj(Si−Sj⩾0) 其中 dp0=1dp_0=1dp0=1。 可是这样的时间复杂度为 O...
2023-08-24
对于DP颜色类问题的切换方法：P9561
对于dp颜色类问题的切换方法：P9561 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471731 对于dp颜色类问题的切换方法 两种颜色为例，一般情况下 dp[i][0]dp[i][0]dp[i][0] 可以由 dp[j][0/1]dp[j][0/1]dp[j][0/1] 在某些情况下转移 但从0到0的过程中，对于 jjj 前的1，可能 jjj 满足，但 iii 不满足 此时可以考虑0只从1转移，1只从0转移，对于新的0，我们除了统计当前dp值，我...
2022-04-25
【GDOI2022PJD2T4 机器人】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人 题目 刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...