RainAir
My OI Blog
RainAir

平衡树
文章归档

Splay 如何维护区间信息

如何维护区间 我们都知道平衡树是一种很神奇的东西,可以用于维护动态的序列总信息,但是如果想维护其中的某一个区间的信息,我们该怎么做好呢? 我们考虑换一种维护方式:平衡树的结构不是按照节点的值的大小来进行建树,而是以这个节点在序列中的位置为关键字来维护…

   496   2019-02-02 去围观

「BZOJ4906」「BJOI2017」喷式水战改

题目链接 题目大意是对于每种物品被划分到不同的组里会产生不同的贡献,求一种最大的划分(这里的划分是连续一段划分到一起),并且要动态维护这个东西。 我们首先考虑静态如何做这个东西,显然我们可以设出一个极为暴力的状态:$f(l,r,i,j)$ 表示燃料 $[l,r]$ 使用…

   393   2019-02-01 去围观

Splay 学习笔记 · 续

之前我写的 平衡树学习笔记 大体介绍了一下两种平衡树。这里详细的介绍 Splay 。 主要是从代码层面详细介绍,默认读者已经掌握了基本原理。 Splay 代码详解 结构体定义 [crayon-5d82873a77d6f823509340/] $ch$ 指针指向这个节点的左右儿子,$val$ 表示该节点表示…

   339   2018-10-28 去围观

平衡树学习笔记

定义 什么叫平衡树?就是看起来很平衡的树。 它是一种中序遍历有序的一棵搜索树,满足左儿子的权值<自身权值<右儿子的权值 它是递归定义的。 算法 目前平衡树的算法很多,在OI中,我们常使用Treap和Splay<(set) 平衡的概念有高度平衡,重量平衡等。 …

   401   2018-05-02 去围观
标签
近期评论