2175 字
11 分钟
笛卡尔树

1. 简介#

笛卡尔树是一种特殊的二叉树,由一系列键值对 (k,w)(k, w) 构成。它同时满足以下两个特性:

  1. 二叉搜索树(BST)性质:节点的左子树中所有节点的 kk 值均小于根节点的 kk 值,右子树中所有节点的 kk 值均大于根节点的 kk 值。
  2. 堆(Heap)性质:节点的 ww 值满足堆的性质(大根堆或小根堆)。通常在算法竞赛中,默认 ww 满足小根堆性质,即父节点的 ww 值小于其子节点。

核心结论:如果一棵树的所有 kk 互不相同,且所有 ww 也互不相同,那么这棵笛卡尔树的结构是唯一的。


2. 基本性质#

以数组 AA 为例,通常将数组下标作为 kk,数组元素值作为 ww:

  • 中序遍历:笛卡尔树的中序遍历结果即为原序列(按 kk 排序)。
  • 区间最值:在小根堆性质下,一段区间 [l,r][l, r] 的最小值对应笛卡尔树中下标 ll 和下标 rr 两个节点的最近公共祖先(LCA)。
  • 子树区间性:笛卡尔树中,以节点 ii 为根的子树,其所有节点在原数组中构成一个连续的区间。

3. 线性构建算法 (O(n)O(n))#

利用单调栈可以在 O(n)O(n) 时间内完成构建。

构建原理#

  1. 按 kk(下标)从小到大的顺序依次插入节点。
  2. 新插入的节点必然位于当前树的右链(从根节点出发一直往右走的路径)上。
  3. 使用单调栈维护这条右链:
    • 比较栈顶节点与当前节点的 ww 值。
    • 如果栈顶 w>w > 当前 ww,说明栈顶节点应该成为当前节点的左孩子(满足堆性质和 kk 的顺序)。
    • 不断弹出直到找到一个 w<w < 当前 ww 的节点,将当前节点设为其右孩子。

复制于oiwiki的建树图 Pasted image 20260124185416


CSES Mountain Range 代码

#include <bits/stdc++.h>
#include <unordered_map>
#define N 1000005
#define ll long long
#define inf 100000000000
using namespace std;
ll n, m, ans;
ll c[N];
const ll mod = 1e9 + 7;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
vector<ll> s(n + 5, 0);
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
stack<int> sta;
int root = 0;
vector<int> rs(n + 5, 0);
vector<int> ls(n + 5, 0);
auto build = [&]() {
for (int i = 1; i <= n; i++) {
int pre = -1;
while (sta.size() && s[sta.top()] < s[i]) {
pre = sta.top();
sta.pop();
}
if (sta.size())
rs[sta.top()] = i;
else
root = i;
if (pre != -1)
ls[i] = pre;
sta.push(i);
}
};
#define lc ls[x]
#define rc rs[x]
build();
vector<int> dis(n + 5, 0);
auto dfs = [&](auto &&self, int x) -> int {
if (!x)
return dis[x] = 0;
int res = 1;
if (lc) {
self(self, lc);
if (s[x] == s[lc])
res = max(dis[lc], res);
else
res = max(dis[lc] + 1, res);
}
if (rc) {
self(self, rc);
if (s[x] == s[rc])
res = max(dis[rc], res);
else
res = max(dis[rc] + 1, res);
}
return dis[x] = res;
};
cout << dfs(dfs, root);
return 0;
}

4. Codeforces 2269E:KiaKio and Energy Intervals#

题目重述#

给定长度为 nn 的数组 aa。选择一个满足 l<rl<r 的区间 [l,r][l,r],令

m=max⁡(al,al+1,…,ar).m=\max(a_l,a_{l+1},\ldots,a_r).

区间的能量定义为

val⁡(l,r)=⨁i=lr(ai&m).\operatorname{val}(l,r)=\bigoplus_{i=l}^{r}(a_i\mathbin{\&}m).

求所有合法区间中的最大能量。

约束为 1≤t≤1041\le t\le 10^4、2≤n≤2⋅1052\le n\le 2\cdot 10^5,所有测试用例的 nn 之和不超过 2⋅1052\cdot 10^5,且 0≤ai<2180\le a_i<2^{18}。

关键观察#

按位贪心转化为可行性判定#

设 MM 是当前希望强制出现在答案中的位掩码。定义 check(M):是否存在一个区间,使其能量的所有 MM 中的位均为 11。

若该区间的最大值为 axa_x,则必须满足

(ax&M)=M,(a_x\mathbin{\&}M)=M,

否则能量中不可能出现 MM 的某个高位。满足该条件后,令 bi=ai&Mb_i=a_i\mathbin{\&}M,则每个 bib_i 都只包含 MM 中的位,因此区间异或包含全部 MM 中的位,当且仅当

⨁i=lrbi=M.\bigoplus_{i=l}^{r}b_i=M.

记前缀异或

pi=b1⊕b2⊕⋯⊕bi,p_i=b_1\oplus b_2\oplus\cdots\oplus b_i,

则判定条件变成 pl−1⊕pr=Mp_{l-1}\oplus p_r=M。

从最高位到最低位依次尝试加入一位:若 check(ans | (1 << bit)) 成立,就保留该位。因为数值比较首先由最高不同位决定,该过程得到所有可行能量中的最大值。

用最大笛卡尔树确定区间最大值#

以数组下标为键、aia_i 为权值建立最大笛卡尔树。代码在建树时仅弹出严格更小的栈顶,因此相同最大值保留在左侧节点的右子树中;于是每个区间的树根可视为该区间最大值最左侧的出现位置。

设节点 xx 的子树对应数组区间 [Lx,Rx][L_x,R_x]。节点 xx 是某个区间的笛卡尔树根,当且仅当

Lx≤l≤x≤r≤Rx.L_x\le l\le x\le r\le R_x.

这是因为子树区间内的元素都不大于 axa_x,而区间一旦越过子树边界,就会包含笛卡尔树中位于 xx 上方的更大(或按相同值规则优先的)节点。

跨过根节点的区间等价于前缀异或配对#

固定节点 xx,只考虑其根为 xx 的区间。左端点对应的前缀下标 l−1l-1 位于 [Lx−1,x−1][L_x-1,x-1],右端点对应的前缀下标 rr 位于 [x,Rx][x,R_x],因此需要寻找

pi⊕pj=M,i∈[Lx−1,x−1],j∈[x,Rx].p_i\oplus p_j=M, \quad i\in[L_x-1,x-1],\quad j\in[x,R_x].

代码的 dfs(x, l, r) 使用前缀下标约定表示节点 xx 的子树数组区间 [l+1,r][l+1,r]。所以两个待配对集合正好是 l..x-1 与 x..r。

启发式合并与非法单点区间#

在节点 xx 处,将较大一侧的 pre 值加入频次数组 cnt,枚举较小一侧的每个 pip_i,查询 cnt[p_i ^ M]。较小一侧的元素只会被重新加入到更大的集合中,因此一次 check 的复杂度为 O(nlog⁡n)O(n\log n)。

上述配对会额外包含 i=x−1,j=xi=x-1,j=x,它对应区间 [x,x][x,x],但题目要求 l<rl<r。若

px−1⊕px=M,p_{x-1}\oplus p_x=M,

则代码在对应的小集合位置上减去这一个频次,排除该非法配对;这正是变量 bad 与 badid 的作用。

解析#

对每个测试用例执行以下步骤:

  1. 使用单调栈在线性时间内建立最大笛卡尔树。栈中维护当前右链;新节点弹出所有权值更小的节点,最后一个被弹出的节点成为新节点的左孩子,栈顶成为新节点的父节点的右孩子。
  2. 枚举答案的二进制位。对每个候选掩码 MM,先计算 pip_i。
  3. 在笛卡尔树上进行启发式合并 DFS。递归处理左右子树后,使用 cnt 检查所有跨过当前节点 xx 的前缀异或配对;仅当 (ax&M)=M(a_x\mathbin{\&}M)=M 时才进行检查。
  4. 如果存在合法配对,则当前位可以加入答案。

正确性来自三点:笛卡尔树将每个区间唯一归类到其最大值根节点;前缀异或将固定根节点下的区间条件准确转换为两个集合间的异或配对;check(M) 判定的正是“存在一个能量包含掩码 MM 的区间”。因此按位贪心在每一位都保留了数值最优的可行前缀,最终得到全局最大能量。

设 B=21B=21 为代码枚举的位数。建树复杂度为 O(n)O(n),每次判定复杂度为 O(nlog⁡n)O(n\log n),总复杂度为

O(Bnlog⁡n),O(Bn\log n),

空间复杂度为

O(n+2B)。O(n+2^B)。

代码#

#include <bits/extc++.h>
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define sp << ' ' <<
#define inf 0x3f3f3f3f3f3f3f3f
#define N 100005
using namespace std;
using namespace __gnu_pbds;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
vector<ll> cnt(1 << 21, 0);
auto solve = [&]() {
ll n, root;
cin >> n;
vector<array<int, 2>> tr(n + 5, {0, 0});
stack<int> sta;
vector<int> s(n + 5, 0);
vector<int> pre(n + 5, 0);
for (int i = 1; i <= n; i++) {
cin >> s[i];
int pre = -1;
while (sta.size() && s[sta.top()] < s[i])
pre = sta.top(), sta.pop();
if (sta.size())
tr[sta.top()][1] = i;
else
root = i;
if (pre != -1)
tr[i][0] = pre;
sta.push(i);
}
ll ans = 0;
auto check = [&](int M) -> bool {
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] ^ (s[i] & M);
}
bool found = false;
auto dfs = [&](auto &&self, int x, int l, int r, bool keep) -> void {
if (l == r) {
if (keep)
cnt[pre[l]]++;
return;
}
int lc = tr[x][0], rc = tr[x][1];
bool leftSmall = x - 1 - l <= r - x;
int sl = leftSmall ? l : x, sr = leftSmall ? x - 1 : r;
if (leftSmall)
self(self, lc, l, x - 1, false), self(self, rc, x, r, true);
else
self(self, rc, x, r, false), self(self, lc, l, x - 1, true);
if ((s[x] & M) == M) {
bool bad = (pre[x - 1] ^ pre[x]) == M;
int badid = leftSmall ? x - 1 : x;
for (int i = sl; i <= sr; i++) {
if (cnt[pre[i] ^ M] - (bad && badid == i) > 0)
found = true;
}
}
for (int i = sl; i <= sr; i++)
cnt[pre[i]]++;
if (!keep)
for (int i = l; i <= r; i++)
cnt[pre[i]]--;
};
dfs(dfs, root, 0, n, false);
return found;
};
for (int i = 20; i >= 0; i--) {
if (check(ans | (1 << i)))
ans |= (1 << i);
}
cout << ans << '\n';
};
ll t;
cin >> t;
while (t--)
solve();
return 0;
}
笛卡尔树
https://sanzenin.top/posts/obsidian/笛卡尔树/
作者
Sanzenin 凪
发布于
2026-10-04
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取