[题解] ZJOI2019 线段树
题目描述 九条可怜是一个喜欢数据结构的女孩子,在常见的数据结构中,可怜最喜欢的就 […]
题目描述 九条可怜是一个喜欢数据结构的女孩子,在常见的数据结构中,可怜最喜欢的就 […]
题目描述 Y901 高速公路是一条重要的交通纽带,政府部门建设初期的投入以及使用 […]
$\mathrm{FHQ} \ \mathrm{Treap}$ 是一类基于 $\mathrm{Split}$ 和 $\mathrm{Merge}$ 操作的平衡树,不需要旋转的特性是可持久化平衡树的基础
Kruskal 重构树是一种基于 Kruskal 算法,在求解最小生成树的同时建出一棵新树。Kruskal 重构树是一个二叉堆,原图两点之间边权最大值等于 Kruskal 重构树上 LCA 权值
替罪羊树(重量平衡树)和 Treap (树堆)也是两种常用的平衡树,分别基于平衡因子和随机附加域来保证子树的平衡。
可持久化线段树是一种能支持访问历史版本的线段树,能实现基于某一个历史版本的操作。主席树和可持久化线段树一般是等价的,但更多时候主席树一般是一棵权值(值域)线段树
一道线段树套平衡树的模板题,支持在区间中完成平衡树的相关功能,本题可以在 $O(log^2 n)$ 的时间内进行区间单点修改,查询某一个区间内的前驱,后继,排名,并通过二分的方法,在 $O(log^3 n)$ 的时间内查询区间 $k$ 小值。
题目描述 小仓鼠的和他的基(mei)友(zi)sugar 住在地下洞穴中,每个节 […]
题目描述 有两个长度都是 $N$ 的序列 $A$ 和 $B$ ,在 $A$ 和 […]
权值线段树较普通线段树不同地方在于:权值线段树的数组范围 $n$ 是它的值域大小 […]