当前位置: 首页 > news >正文

笛卡尔树

\(\text{Part 1.}\) 笛卡尔树是什么和其构建方法

笛卡尔树是一个二叉树,对于这棵树上的每一个节点,其都有两个值 \((k,w)\),其中 \(k\) 满足二叉搜索树的性质,\(w\) 满足堆的性质。如果所有的 \(k\) 和所有的 \(w\) 均不相同,那么笛卡尔树就是唯一的。

而根据如上的定义,Treap 也是一颗笛卡尔树。

下面就是一个笛卡尔树的例子:

其中对于节点 \(i\),他的两个键值就是 \((i,a_i)\)。而如果在笛卡尔树中 \(w\) 满足小根堆的性质,那么我们称这棵笛卡尔树为小根笛卡尔树。

那么他是如何构建的呢?现在考虑对于一个序列 \(a\) 建笛卡尔树。

由于下下标肯定是单增的,所以新插入的点只能是已前面点的右儿子、前面点只能是它的左儿子。

所以此时考虑使用单调栈维护一个权值单调递增的下标序列。那么在插入一个新点的时候,这个点就是第一个比它小的点的右儿子。比这个新点大的最后一个点作为这个新点的左儿子。

code:

void build()
{for(int i = 1;i <= n;i++){int pos = 0;while(top && a[stk[top]] > a[i])pos = stk[top],top--;if(top)ch[stk[top]][1] = i;ch[i][0] = pos;stk[++top] = i;}
}

注意笛卡尔树的模板题卡常。

http://www.wuyegushi.com/news/499.html

相关文章:

  • 如何获取集合控件中子项元素的容器
  • 火山引擎-大模型应用防火墙
  • chorme如何设置在新标签页打开页面?
  • Gentoo解决clocksource未使用tsc问题
  • UIUCTF 2024 syscalls
  • POLIR-Laws-民法典: 第三编 合同 : 第二分编 典型合同: 17.承揽
  • 2025-07-27 模拟赛总结
  • widedeep在adult数据集上的应用
  • POLIR-Laws-民法典: 第三编 合同 : 第二分编 典型合同
  • 协议版iM蓝号检测,批量筛选iMessages数据,无痕检测是否开启iMessage服务
  • 2025年7月27日
  • 连续动作强化学习中的反事实探索:揭示AI决策背后的可能性
  • ADC模数转换器
  • 启明星辰-大模型应用防火墙
  • VulnHub 靶场--broken(十六进制转图片)
  • TIM输入捕获
  • 文件权限标记机制在知识安全共享中的应用实践
  • PID
  • POLIR-Laws-民法典: 民法典 包括 并 废止 《合同法》
  • 18
  • 字节-大模型联邦精调方案
  • 分块
  • 并查集
  • 7-27
  • CVE-2021-21311 服务器端请求伪造(SSRF)漏洞 (复现)
  • 【Rag实用分享】小白也能看懂的文档解析和分割教程
  • 【纯干货】三张图深入分析京东开源Genie的8大亮点
  • JoyAgent综合测评报告
  • 【EF Core】为 DatabaseFacade 扩展“创建”与“删除”数据表功能
  • 亚马逊机器学习大学推出负责任AI课程 - 聚焦AI偏见缓解与公平性实践