笛卡尔树(超详细!!!)
in 算法 with 0 comment

笛卡尔树(超详细!!!)

in 算法 with 0 comment

0x01 介绍

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

笛卡尔树每一个结点由一个键值二元组$(k,v)$构成。要求$k$满足二叉搜索树的性质,而$v$满足堆的性质。如图:

上面这棵笛卡尔树相当于把数组元素值当作键值$v$,而把数组下标当作键值$k$。显然可以发现,这棵树的键值$k$满足二叉搜索树的性质,而键值$v$满足小根堆的性质。

其实图中的笛卡尔树是一种特殊的情况,因为二元组的键值$k$恰好对应数组下标,这种特殊的笛卡尔树有一个性质,就是一棵子树内的下标是连续的一个区间(这样才能满足二叉搜索树的性质)。更一般的情况则是任意二元组构建的笛卡尔树。

0x02 构建

我们考虑将元素按照键值$k$排序,然后一个一个插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这个树的右链(右链:即从根结点一直往右子树走,经过的结点形成的链)的末端。这里采用单调栈(单调递增栈)构建笛卡尔树,栈中维护当前笛卡尔树的右链上的结点。

int st[N], ls[N], rs[N], n, A[N];// ls代表笛卡尔树每个节点的左孩子,rs代表笛卡尔树每个节点的右孩子
int top = 0;

for (int i = 1; i <= n; ++i) 
{
    while (top && A[st[top]] > A[i]) ls[i] = st[top--]; //栈顶元素为当前元素的左孩子
    if (top) rs[st[top]] = i; //当前元素为栈顶元素的右孩子
    st[++top] = i;
}

reference:

https://zh.wikipedia.org/wiki/笛卡尔树

https://oi-wiki.org/ds/cartesian-tree/

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses