在我们之前接触到的题目里面，线段树的叶子节点都是保存单点的值，其他节点都是保存一个区间的值，这种题目的一些基本构造想法在浅谈线段树的构造(一)中已经提及到了。但你想过吗，当叶子节点保存一个区间的值时，你该如何构造？ 从经典的例题谈起 我们先看一道POI2015的经典例题： 【BZOJ p3747】[POI2015]Kinoman Time Limit: 60 Sec Memory L...
在上一篇BLOG中，我们介绍了二叉查找树的八种操作。但是有人会说，万一退化成链之类的不就超时了吗？为了让我们的二叉查找树高度的期望维持在 log n ，我们就要通过平衡树来进行一些维护。而今天我们就来介绍一种神奇的平衡树——TREAP 写在前面：如果你还不太熟悉二叉查找树，建议先抽空点我学习二叉查找树后再食用这篇BLOG. 什么是Treap 我们都知道，Treap是平衡树的一种实现形式，...
在学习平衡树和Splay之前，我们应该了解一个更为基础的算法——二叉查找树。不论是平衡树还是splay都是建立在二叉查找树上，所以这篇BLOG，我就来带领你走进二叉查找树。 二叉查找树的定义 二叉查找数不同于普通二叉树的一个特点就是:对于每一个节点，若存在左子节点，那么该节点的值一定大于左子节点的值；若存在右子节点，那么该节点的值一定小于右子节点的值，例如下图就是一棵可爱的二叉查找树： ...
说到线段树，大家第一反应就是经典的RMQ问题，相信大家都已经很好的掌握了，今天就不再过多的进行讲解了。今天我们主要通过一道例题开始，浅谈一下线段树的构造吧。 一道水题 我们先从一道简单的例题看起。 给你一段长为n，n≤1e5 的47串，比如4747747444774…………，求这个串的最长不下降子序列的长度是多少(PS 子序列即不一定要连续的串)。 “这不是一道惊天大水题吗”看完后的你一...
杭州OI学习之旅Day1打卡——看似神奇实则平实的的左偏树。今天在陈学长的带领之下学习了堆和左偏树，这篇BLOG，就让我们一同走进左偏树吧。 【PS 参考资料 黄源河《左 偏 树 的 特 点 及 其 应 用》】 堆 左偏树的实质是一个可并堆，在了解可并堆之前我们需要先了解堆。 堆是什么？看起来很高级，但其实它就是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时...