当前位置：首页 > ds >正文

[多彩数据结构] 笛卡尔树

ds 2025/7/2 2:17:41

[多彩数据结构] 笛卡尔树

定义

笛卡尔树，就是一棵树（废话）中存两个信息，为 $(w, i)$ 。其中 $k = w e i g h t, i = i d$ 。

即 $w$ 存的是节点的值， $i$ 存的是编号。

每棵笛卡尔树都对应着一个排列，这点很重要（伏笔）。

下面给出一个标准的笛卡尔树。

$w$ 满足堆的性质

这为我们后面操作提供了 $\log n$ 的时间复杂度。

$i$ 满足二叉搜索树的性质。

啥意思呢？就是抽象下，在一维内，每个 $i$ 都是从左到右递增。图：

~~画技高超~~

性质：

若每个节点的 $(k, i)$ 互不相同，那么整棵笛卡尔树也是独一无二的。

构建

可以按照性质从根自上而下构建笛卡尔树。

因为之前说过：

每棵笛卡尔树都对应着一个排列，这点很重要（伏笔）。收回伏笔。

节点的编号满足排序树的性质，值满足堆的性质。

以下以小根堆举例子。

那么我们可以选取当前序列的最小值为根，并将序列划分为了两个子树。

左子树的 $k$ 是小于根的 $k$ 值的，右子树是大于根的 $k$ 值的。（此乃二叉搜索树的性质）

如图。

然后，我们再慢慢处理子问题。

由于 $w$ 遵守堆的性质，那么我们就需要去找区间最值。啥办法？线段树？ST 表？树状数组？只想说：都太慢！！！！

如何插入？

不妨换个角度思考，按照编号由小到大构建笛卡尔树，此时需要在右边插入节点。

这时候就知道这东西的好处了吧 $\downarrow \downarrow \downarrow \downarrow \downarrow$

在一维内，每个 $i$ 都是从左到右递增。

如果新插入的节点的值是最大的，那么根据小根堆的性质，应当作为当前编号最大节点的右儿子。如 $w = 9$ 的那位。

否则，应当从当前按编号最大节点自底向上寻找合适的位置插入。

如 $w = 6$ 的那位。

你给新节点找到一个合适位置安家的时候，应当满足什么性质呢？

你的父亲节点的值刚好比它小
你的儿子节点的值刚好比它大

这些也是堆和排序树的性质。

哦对，排序树好像就是二叉搜索树。

你一定会不停地往上找，直到满足以上条件。

无论到什么地方，靠下部分都只能作为虚拟节点的左子树，新节点爷只能作为靠上部分的右儿子。

多么通俗易懂。

因为编号只增不减，所以一定是上边的右儿子。另一个同理。

现在我们需要维护一个序列。它是从根开始不断像右儿子移动的序列。因为是从下往上跳，所以可以用栈 stack 来维护。

实现思路

按照编号顺序依次插入每个节点

1.1.若栈顶节点的值还大于新节点

1.1.1 将新节点的左儿子重置为栈顶节点

1.1.2 删除栈顶节点，并重复1.1步骤

1.2 将栈顶节点的右儿子重置为新节点

1.3 将新节点入栈

看看是不是很像单调栈？

Code：

for(ljl i=1;i<=n;++i)//ljl = long long{cin>>node[i].v;while(!st.empty()/*栈不空*/&&node[st.top()].v>node[i].v/*没有找到合适位置*/)node[i].l=st.top(),st.pop();//操作1.1.1 and 1.1.2if(!st.empty())//这里如果没特判空栈貌似会炸吧。。node[st.top()].r=i;//操作1.2st.push(i);//1.3}

例题：

洛谷 P5854 【模板】笛卡尔树。

AC CODE:

#include<bits/stdc++.h>
using namespace std;
#define ljl long long//不开long long 见祖宗
const ljl N=1e7+5;
ljl n,ans1,ans2;
struct NODE{ljl v,l,r;
}node[N];
stack<int> st;
int main(){ios::sync_with_stdio(0);cin>>n;for(ljl i=1;i<=n;++i){cin>>node[i].v;while(!st.empty()&&node[st.top()].v>node[i].v)node[i].l=st.top(),st.pop();if(!st.empty())node[st.top()].r=i;st.push(i);}for(ljl i=1;i<=n;++i){ans1=ans1^(i*(node[i].l+1));ans2=ans2^(i*(node[i].r+1));}cout<<ans1<<' '<<ans2<<'\n';return 0;
}