笛卡尔树详解

笛卡尔树详解笛卡尔树 笛卡尔树

大家好,欢迎来到IT知识分享网。

Part 1:定义

笛卡尔树是一种每个节点有两个关键字 ( k , w ) (k, w) (k,w),且第一关键字 k k k 构成的树满足二叉搜索树的性质,第二关键字 w w w 构成的树满足堆的性质的树。

(这里有点绕,可以根据图理解一下)

这里放了OI Wiki 上的一棵特殊的笛卡尔树。
笛卡尔树详解
在这棵树中,数组下标对应的是元素的第一关键字,数组的值对应的是元素的第二关键字。

不难发现,在上图中,每一棵子树对应的下标是一个连续的区间。

在一般的笛卡尔树中,第一关键字不一定是 1 1 1 n n n 的排列,可以为任意的值。

Part 2:性质

一般地,笛卡尔树经第一关键字排序后,一个子树中的节点对应的下标,是一个连续的区间

下文中的性质及建树,都指按照第一关键字 k k k 排序后的点集。

由于笛卡尔树中元素的第一关键字构成的树满足二叉搜索树的性质,所以在添加元素时,应当将节点添加在当前树的右链上。
如下图:
笛卡尔树详解在图中,所添加的节点要么是根,要么是叶子结点,要么是插在右链的中间。

插在右链中间时,在它下面的子树,会变成该节点的左子树。
即:插入后它下面的那一个节点,会成为它的儿子。

Part 3:建树

根据排好序的顺序,逐个加点。

因为笛卡尔树满足堆的性质,上面的节点一定大于(或小于)下面的节点。所以,从右链的最下端开始扫描,直到扫到合适的位置(即第二关键字处于当前点两侧的两个点),插入即可。

插入点时,直接将该点压到栈顶。

由于弹出的元素会变成左子树,不会出现在右链中,所以可以证明该做法是正确的。

参考代码:

void insert() { 
    stack<int> st; // 记录右链节点的编号  int last_pop = 0; // 最后弹出节点的编号  for (int i = 1; i <= n; ++i) { 
    int sz = st.size(); while (st.size() && nd[st.top()].w > a[i]) last_pop = st.top(), st.pop(); // 本代码中是小根堆,k为 1~n  if (st.empty()) { 
    // 若扫完后栈为空,说明该节点应成为根  root = i; nd[i].lc = last_pop; // 原来的树成为左子树  } else if (st.size() == sz) { 
    // 没有弹出元素,该点成为叶子  nd[st.top()].rc = i; } else { 
    // 插在中间  nd[i].lc = last_pop; // 左子结点  nd[st.top()].rc = i; } nd[i].w = a[i]; // w记录第二关键字  st.push(i); // 压进栈  } } 

Part 4:例题

Luogu P5854 : 【模板】笛卡尔树

题目描述

给定一个 1 ∼ n 1 \sim n 1n 的排列 p p p,构建其笛卡尔树。

即构建一棵二叉树,满足:

  1. 每个节点的编号满足二叉搜索树的性质。
  2. 节点 i i i 的权值为 p i p_i pi,每个节点的权值满足小根堆的性质。

输出格式

l i , r i l_i,r_i li,ri 分别表示节点 i i i 的左右儿子的编号(若不存在则为 0 0 0)。

一行两个整数,分别表示 xor ⁡ i = 1 n i × ( l i + 1 ) \operatorname{xor}_{i = 1}^n i \times (l_i + 1) xori=1ni×(li+1) xor ⁡ i = 1 n i × ( r i + 1 ) \operatorname{xor}_{i = 1}^n i \times (r_i + 1) xori=1ni×(ri+1)

样例输入

5 4 1 3 2 5 

样例输出

19 21 

【样例解释】

i i i l i l_i li r i r_i ri
1 1 1 0 0 0 0 0 0
2 2 2 1 1 1 4 4 4
3 3 3 0 0 0 0 0 0
4 4 4 3 3 3 5 5 5
5 5 5 0 0 0 0 0 0

【数据范围】

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 7 1 \le n \le 10^7 1n107

计算出每个节点的左右儿子,再统计答案即可。
代码:

#include <bits/stdc++.h> using namespace std; #define int long long // 不开 long long 见祖宗  const int N = 1e7 + 5; inline int read() { 
    // 快读  int x = 0, f = 1; char c = getchar(); while (!isdigit(c)) { 
    if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } struct Node { 
    int lc, rc; int w; }nd[N]; // 记录节点信息  int n; int a[N]; int root = 0; void insert() { 
    // 同上  stack<int> st; // 记录节点的编号  int last_pop = 0; // 最后弹出的节点的编号  for (int i = 1; i <= n; ++i) { 
    int sz = st.size(); while (st.size() && nd[st.top()].w > a[i]) last_pop = st.top(), st.pop(); if (st.empty()) { 
    // 若扫完后栈为空,说明该节点应成为根  root = i; nd[i].lc = last_pop; // 原来的树成为左子树  } else if (st.size() == sz) { 
    // 没有弹出元素,该点成为叶子  nd[st.top()].rc = i; } else { 
    // 插在中间  nd[i].lc = last_pop; // 左子结点  nd[st.top()].rc = i; } nd[i].w = a[i]; // w记录第二关键字  st.push(i); // 压进栈  } } signed main() { 
    cin >> n; for (int i = 1; i <= n; ++i) { 
    a[i] = read(); } insert(); // 统计左右儿子(构建笛卡尔树)  int ans1 = 0, ans2 = 0; for (int i = 1; i <= n; ++i) { 
    // 统计答案  ans1 ^= i * (nd[i].lc + 1); ans2 ^= i * (nd[i].rc + 1); } cout << ans1 << ' ' << ans2; } 

参考文献:

OI Wiki – 笛卡尔树

感谢阅读!

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/125998.html

(0)
上一篇 2025-09-22 16:15
下一篇 2025-09-22 16:20

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信