[关闭]
@Bei-S 2019-01-10T07:07:39.000000Z 字数 942 阅读 367

笛卡尔树学习笔记

数据结构


世人的烦恼多来源于书读的不多。

却想的太多。

——杨绛


笛卡尔树:

笛卡尔树结构由Vuillmin在解决范围搜索的几何数据结构问题时提出的,从数列中构造一棵笛卡尔树可以线性时间完成,需要采用基于栈的算法来找到在该数列中的所有最近小数。由此可知,笛卡尔树是一种特定的二叉树数据结构,可由数列构造,在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。它具有堆的有序性,中序遍历可以输出原数列。[From 百度]

定义:

构造:

  1. for (int i=1;i<=n;i++){
  2. read(key[i]),val[i]=rand();
  3. while (top&&val[i]<val[stack[top]]){
  4. lson[i]=stack[top];
  5. top--;
  6. }
  7. if (top) rson[stack[top]]=i;
  8. stack[++top]=i;
  9. }

用处:

主要用于的构建
当题目Key给定时,用普通方法构造一些数据可以把树高卡成,复杂度变为而此时用笛卡尔树的构造方法为稳定

同时在构造时也需要用笛卡尔树的构建方法,因为非旋转式Treap的需要一次和两次,常数略大,用笛卡尔树建树比较快。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注