本文主要是介绍初学 笛卡尔树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

表示之前没见过这种东西。

概念

Link

构造

知乎

以下均假设原序列元素两两不相同。

从左至右依次加入元素，维护当前笛卡尔树的右耳子链

至一个栈内。

设加入的节点为 \(x\)，\(t\) 为当前笛卡尔树。

1. 找到栈中最靠顶部的节点 \(y\) 使得 \(val[y]<val[x]\)。

2. 特判 \(y\) 为栈顶，直接 \(t[y].rson:=x\) 即可结束。

3. 记栈中 \(y\) 的楼上为 \(z\)

时间 \(O(n)\)

这篇关于初学 笛卡尔树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！