笛卡尔树:
笛卡尔树是关于多个二元组 \((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;
}
- 性质:
-
一个节点 \(u\) 的子树内的子节点的值一定均小于等于该节点的值,若它的管辖区间是 \([l, r]\),则对于 \(\forall l', r', l \le l' \le u \le r' \le r\),则 \(\max_{i = l'}^{r'}a_i = a_u\)。
-
一个区间 \([l, r]\) 的最值位置是 \(l\),\(r\) 在笛卡尔树上的 \(\rm LCA\)。
-
对于一个 \(a_i\),它左边第一个大于等于它的 \(a_j\) 在笛卡尔树上是它向左的拐点祖先,右边同理。
-
对于一个有 \(n\) 个节点且随机的笛卡尔树,树高期望为 \(\log n\)。