标签平衡树下的文章

「算法笔记」FHQ-Treap

$\text{FHQ-Treap}$ 是一种无旋 $\text{Treap}$，它不但能够兼容其他平衡树所涉及的问题，而且可以轻松地进行可持久化。

Siyuan 2019 年 03 月 19 日暂无评论

题目链接：BZOJ 1500

请写一个程序，要求维护一个数列。一共有 $m$ 个操作，支持以下 $6$ 种操作：

操作	输入格式	说明
插入	`INSERT post tot c[1] c[2] ... c[tot]`	在当前数列的第 $pos$ 个数字后插入 $tot$ 个数字：$c_1,c_2,\cdots,c_{tot}$；若在数列首插入，则 $pos$ 为 $0$。
删除	`DELETE pos tot`	从当前数列的第 $pos$ 个数字开始连续删除 $tot$ 个数字。
修改	`MAKE-SAME pos tot c`	将当前数列的第 $pos$ 个数字开始的连续 $tot$ 个数字统一修改为 $c$。
翻转	`REVERSE pos tot`	取出从当前数列的第 $pos$ 个数字开始的 $tot$ 个数字，翻转后放入原来的位置。
求和	`GET-SUM pos tot`	计算从当前数列的第 $pos$ 个数字开始的 $tot$ 个数字的和并输出。
求和最大的子列	`MAX-SUM`	求出当前数列中和最大的一段非空子列，并输出最大和。

数据范围：$1\le m\le 2\times 10 ^ 4$，任何时刻数列中最多含有 $5\times 10 ^ 5$，数列中任何一个数字均在 $[-10^3,10^3]$，插入的数字总数不超过 $4\times 10 ^ 6$ 个。

Siyuan 2019 年 03 月 15 日 3 条评论

$\text{Splay}$ 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。

Siyuan 2019 年 03 月 14 日 2 条评论

$\text{Splay}$ 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。

Siyuan 2019 年 02 月 07 日暂无评论