首页 > 其他分享 >笛卡尔树

笛卡尔树

时间:2024-07-24 16:07:36浏览次数:10  
标签:le 笛卡尔 top stk 节点 最值

笛卡尔树:

笛卡尔树是关于多个二元组 \((k_i,w_i)\) 的一棵树,使其所有 \(k\) 值满足二叉搜索树的性质,且所有 \(w\) 值都满足小根堆的性质。笛卡尔树有一些关于区间最值的美好性质,常常用于处理关于区间最值的问题。

  • 构建方法:

在构建时,对于右链上的元素,自底向上一定是 \(w\) 值由小到大的,且一定 \(k\) 值从小到大。

所以我们按 \(k\) 值从小到大排序,比并按顺序插入右链中。

假设我们轮到第 \(i\) 个元素插入,我们先找到在第一个右链中 \(w\) 值大于 \(w_i\) 的元素下标 \(j\) 。因为这棵树需要满足二叉搜索树的性质,所以我们将 \(j\) 以下的元素接到 \(i\) 的左子树上,并将 \(i\) 接到 \(j\) 的右子树上。

使用栈模拟即可。

qwq
for(int i = 1; i <= n; i++){
		while(top && a[stk[top]] > a[i]) top--;
		ls[i] = stk[top + 1];
		if(top) rs[stk[top]] = i;
		stk[++top] = i; stk[top + 1] = 0;
}
  • 性质:
  1. 一个节点 \(u\) 的子树内的子节点的值一定均小于等于该节点的值,若它的管辖区间是 \([l, r]\),则对于 \(\forall l', r', l \le l' \le u \le r' \le r\),则 \(\max_{i = l'}^{r'}a_i = a_u\)。

  2. 一个区间 \([l, r]\) 的最值位置是 \(l\),\(r\) 在笛卡尔树上的 \(\rm LCA\)。

  3. 对于一个 \(a_i\),它左边第一个大于等于它的 \(a_j\) 在笛卡尔树上是它向左的拐点祖先,右边同理。

  4. 对于一个有 \(n\) 个节点且随机的笛卡尔树,树高期望为 \(\log n\)。

例题:

标签:le,笛卡尔,top,stk,节点,最值
From: https://www.cnblogs.com/little-corn/p/18320162

相关文章

  • 笛卡尔树
    \(\texttt{0x00}\):前置芝士二叉搜索树堆单调栈\(\texttt{0x01}\):概念笛卡尔树是一种二叉树,每一个结点由一个键值二元组\((k,w)\)构成。要求\(k\)满足二叉搜索树的性质(左小右大),而\(w\)满足堆的性质(大根堆或小根堆)。q1:这么一看,Treap不也是笛卡尔树?a1:正确的。一个有......
  • 仅产生 2D 笛卡尔积的上三角形
    我知道如何使用itertools.productIn[19]:fromitertoolsimportproduct...:...:abcd=product('abcd','abcd')...:foriinrange(4):...:print(''.join(repr(t)for_,tinzip(range(4),abcd)))......
  • Franka Robot 如何理解机器人的笛卡尔阻抗运动
    在笛卡尔阻抗模式下,用手将机器人移动到一个新位置后,机器人的行为取决于其控制参数(刚度、阻尼、质量)的设定和外部力的作用。当你将机器人移动到一个新位置并释放它时,以下是可能的情况:高刚度情况下如果机器人的刚度(Stiffness)参数设置较高,意味着机器人对位置偏差有很强的恢复力。当......
  • 笛卡尔树
    笛卡尔树基本概念笛卡尔树是基于一个静态序列\(a\)的,根据这个序列\(a\),我们可以构造出对应的笛卡尔树。笛卡尔树有三点要求需要满足:笛卡尔树是二叉树。笛卡尔树的编号的中序遍历为\(1\simn\),权值中序遍历为\(a\)。笛卡尔树的权值满足大根堆或者小根堆的性质。......
  • Franka 内部关节阻抗控制器和内部笛卡尔阻抗控制器的区别
    Franka机器人内部的关节阻抗控制器和笛卡尔阻抗控制器之间的本质区别如下:1.控制空间关节空间vs.笛卡尔空间:关节阻抗控制器工作在关节空间,即以关节角度、关节速度和关节扭矩为控制变量。笛卡尔阻抗控制器工作在笛卡尔空间,即以末端执行器的位置、速度和力作为控制变量。......
  • Franka libfranka 基于笛卡尔空间位置控制
    #include<array>#include<cmath>#include<iostream>#include<franka/exception.h>#include<franka/model.h>#include<franka/robot.h>#include<franka/tools.h>intmain(intargc,char**argv){try{//......
  • Franka libfranka 基于笛卡尔空间位置的运动控制
    #include<array>#include<cmath>#include<iostream>#include<franka/exception.h>#include<franka/model.h>#include<franka/robot.h>#include<franka/tools.h>intmain(intargc,char**argv){try{//......
  • P5854 【模板】笛卡尔树
    原题链接题解笛卡尔树的定义如下:任意一颗子树都代表一段连续的区间,且子树的根节点是该区间的最大值,根的左边的元素下标均比根小(二叉搜索树性质),子节点均比父节点大(堆的性质)我们讲如何实现的设即将要插入的元素为\(a_i\)栈内的元素为前\(i-1\)个元素构成的笛卡尔树从根一直......
  • 笛卡尔树
    笛卡尔树对于每个区间,找到区间的极值,把这个区间一分为二,这个极值就是这个区间的根,两个部分的根是极值的两个儿子如何求笛卡尔树?以大根堆为例方法一令\(l_i\)表示第\(i\)个元素向左第一个\(\ge\)它的位置,\(r_i\)表示第\(i\)个元素向右第一个\(\ge\)它......
  • 笛卡尔树
    引入首先我们看到这个序列\([9,4,10,1,7,2,3]\),现在我们找到它的最大值\(10\),并从中间劈开,此时分为了两个序列\([9,4]\)和\([1,7,2,3]\),接着对这两个序列继续这样的操作。现在,将劈开后序列最大值和被劈开的数建立父子关系,于是便建立了这个树:这也就是笛卡尔树。笛卡尔树满......