[模板] 笛卡尔树 && RMQ

话说我noip之前为什么要学这种东西...

简介

笛卡尔树(Cartesian Tree) 是一种二叉树, 且同时具有以下两种性质:

1. 父亲节点的值大于/小于子节点的值;
2. 中序遍历的结果为原序列.

笛卡尔树可以实现 (O(n)) 预处理, 均摊 (O(1)) 查询的序列rmq操作.

建立

由于第2条性质, 插入的新节点一定在二叉树的右子树链上.

维护一个右子树链的栈, 进行以下操作:

1. 插入一个新节点 (p)
2. 如果栈顶元素 (u) 的值小于 (p), 弹出 (u), 并将其设为 (p) 的左儿子
   否则, (p) 为 (u) 的右儿子.
3. 最后, 栈顶元素即为树的根.

代码:

//a[] : the sequence
struct tnd{int ch[2];}car[nsz];
int rt,pc=0;
int stk[nsz],top=0;
void build(){
	rep(i,1,n){
		while(top&&a[stk[top]]<a[i])car[i].ch[0]=stk[top--];
		car[stk[top]].ch[1]=i;
		stk[++top]=i;
	}
	rt=stk[1],pc=n;
}

应用

序列RMQ

显然, 建好笛卡尔树后, 两个节点 (p) 和 (q) 的 (lca) 即为以这两点为端点的区间的最大/最小值.

我们可以 (O(log n)) 单次求lca, 或者用 tarjan 均摊 (O(1)) 求 lca. 虽然比 log 快但是常数巨大

当数据随机时, 树高期望 (log n), 因此可以从树顶直接向下找儿子来求RMQ. 常数巨小, 比zkw线段树直接RMQ还小.

跑的比tarjan不知道快到哪里去了

扔一道题
11/1/2018模拟 Max