笛卡尔树和一些杂项数据结构

[[ slider_text ]]

[[ item.c ]]

笛卡尔树和一些杂项数据结构

发布时间 2023-05-26 作者：zhangminchen 来源：算法小站

笛卡尔树 ST表 带权并查集

## 笛卡尔树

笛卡尔树一般针对 $$[1, n]$$ 的**排列**
![](/media/content_img/cartersian-tree_rK4TNqN.png)

### 笛卡尔树的性质

**性质一** 区间 $$[l, r]$$ 最小值 `RMQ`，对应笛卡尔树 $$a_l, a_r$$ 两个节点`LCA`的值
比如 `[2, 6]` 区间，对应笛卡尔树是节点 `5, 6`，那么 `LCA(5, 6) = 1`，区间最小值为 `1`

> 证明，从建树的过程考虑，对于某一棵子树的根 $$p$$，$$p$$ 左方的点都在 $$p$$ 的左子树中，右方的点都在右子树中
  又因为，子树中所有的节点 `subtree(p)`的值**一定会大于**根节点 $$p$$（我们建树的时候就是这样建的）
  如果问询一个区间 $$[l, r]$$ 它包含了根节点，那么 $$l, r$$ 分别处于左子树和右子树中
  那么区间最小值就是根节点，同时根节点也一定是左右子树节点的 `LCA`
  
**性质二** 笛卡尔树的**中序遍历**就是原数组
> 把下标当作权值，可以发现笛卡尔树就是一个二叉搜索树，中序的性质成立

**性质三** 如下图
![](/media/content_img/catersian-tree-02_jZyOdXm.png)

> 引理1 对于笛卡尔树任意点 $$x$$，其子树中的点权值必然 $$> x$$
   要想找到第一个 $$\leqslant x$$ 的点，必然要往父亲处去找
   引理2 对于根 $$x$$ 及其子树，对应以 $$x$$ 作为最小值的**极长区间**，区间外的点权都要 $$< x$$
   
> 引理很容易证明，根据建树的过程，对于区间 $$[l, r]$$，在 $$l-1$$ 或者是 $$r+1$$ 处
   如果点的权值 $$> x$$，那么子树区间可以继续扩张
   
> 记 $$x$$ 右边第一个 $$\leqslant x$$ 的点是 $$y$$
   那么对于$$y$$，$$y$$的左儿子$$x$$，是 $$y$$左边一段**连续的**，权值都大于 $$y$$ 的区间中，**权值最小的点**
   也就是说 `subtree(x) > y,  x = min( subtree(x) )`，同时也有 `y < x`
   记 `y` 的父亲为 `pa(y)`，根据建树过程，`y` 一定在 `pa(y)` 的左边
   所以 `y` 是 `x` 右边第一个 $$\leqslant x$$ 的点
   
> 记 $$x$$ 左边第一个 $$\leqslant x$$ 的点是 $$z$$
   首先 `y -> ancestor(y)` 路径上的点都在 `y` 的右边（根据建树的规则），`z` 位于 `y` 的**左边**
   再根据引理2，我们有 `ancestor(y) > z`，由此 `y > ancestor(y) > z`
   `z` 也一定是 `y` 左边第一个 $$< y$$ 的数，又因为 `x > y`，所以 `x > z`
   从而 `z` 一定是原数组左边第一个 $$\leqslant x$$ 的点
   
### 笛卡尔树的构造
可以用**单调栈**的方法

**性质** 笛卡尔树建树过程中，如果按**前缀**顺序插入
对于根节点 $$p$$，左链已经确定下来了就不会变了，只有右链可能会发生变化
先看下图
![](/media/content_img/catersian-tree-03.png)

大致可以发现，按前缀顺序加入节点 $$p$$，在右链上找到第一个 $$>p$$ 的节点 $$q$$
将其整棵子树拆下来，`subtree(q)` 子树链到 $$p$$ 的左子树上，$$p$$ 的右子树留空
（因为 $$p$$ 此时是最后一个点了，右边没东西了）

可以用**单调栈**维护右链，加入一个元素 $$x$$ 时
*  从单调栈中把 `> x` 的元素弹出，弹出的元素用 `subtree`集合维护
*  此时单调栈中的栈顶元素为 `y`，并且 `y < x`，将 `x` 连到 `y` 的**右儿子**上
   同时把`subtree`连到 `x` 的**左子树**上
   
### 笛卡尔树算法实现
```bash
// T e() 为初始化的值

template<class T, T (*e)()>
struct Cartersian {
    int _n, root;
    vector<T> node;
    vector<int> l, r;

Cartersian() : Cartersian(0) {}

explicit Cartersian(int n) : Cartersian(std::vector<T>(n, e())) {}

// v[0...n-1], node[1...n]
    explicit Cartersian(const std::vector<T>& v) {
        _n = (int)(v.size());

node.push_back(e());
        for (const auto &x : v) node.push_back(x);
        assert(node.size() == _n+1);

root = 0;
        l = vector<int> (_n+1, 0), r = vector<int> (_n+1, 0);
    }

void build() {
        stack<int> stk;
        for (int i = 1; i <= _n; i++) {
            int last = 0;
            while (!stk.empty() && node[stk.top()] > node[i]) {
                last = stk.top();
                stk.pop();
            }

if (!stk.empty()) r[stk.top()] = i;
            else root = i;

l[i] = last;
            stk.push(i);
        }
        for (int i = 1; i <= _n; i++) {
            printf("i: %d,  a[i]: %d,  l[i]: %d,  r[i]: %d\n", i, node[i], l[i], r[i]);
        }
    }
};

// T e()  { return T; }
```

### 笛卡尔树的使用场景

给你 $$n$$ 个数，求区间最小值之和，即 $$\displaystyle \sum\_{i = 1}^{n} \sum\_{j =i+1}^{n} \min (a_i, \cdots, a_j)$$

考虑每一个元素 $$a_i$$，用单调栈处理左边第一个比 $$a_i$$ 小的元素和右边第一个比$$a_i$$ 小的元素位置
假设分别是 $$l_i, r_i$$，那么 $$[l_i+1, r_i-1]$$ 区间都是以 $$a_i$$ 作为最小值的
那么 $$a_i$$ 对答案的贡献是 $$a_i \cdot (i-l_i) \cdot (r_i - i)$$，把所有贡献加起来就是了

换成笛卡尔树，那么对树上的每一个点求贡献，对于点 $$a_i$$，考虑其左子树大小 `lsize`
右子树大小为 `rsize`，那么贡献就是 $$a_i \cdot (\text{lsize} + 1) \cdot (\text{rsize} + 1)$$

**例题** 
给定一个 $$1 \to n$$ 的排列 $$p\_1, \cdots, p\_n$$，构造一个 $$1\to n$$ 的排列$$q$$，使得对任意区间 $$[l, r]$$
满足 $$p\_{l}, p\_{l+1}, \cdots, p\_{r}$$ **最小值的位置**和 $$q\_{l}, q\_{l+1}, \cdots, q\_{r}$$ 相同
输出字典序最小的排列

**算法分析**
最小值的位置相同，那么**笛卡尔树**的拓扑结构一定相同
> 说明，拓扑结构相同，就是建出笛卡尔树后，将**下标看作权值**，笛卡尔树就是一个 BST
> 此时二者的二叉搜索树对应相同

实现起来就很简单了，先根据排列 $$p$$ 建一棵笛卡尔树
然后**先序遍历**这棵笛卡尔树，根节点**填上当前最小的值**（因为笛卡尔树的根必须是最小）
然后 `dfs( l(u) )`，左子树优先把小的数先填满，再填右子树

## 带权并查集
**问题描述**
给定 $$n$$ 个数，$$a_1, \cdots, a_n$$，一开始不知道这些数是多少
执行 $$q$$ 次操作，强制在线

*  `1 l r x` 给出 `a[l] - a[r] = x`，如果与已知条件矛盾，忽略这次操作
*  `2 l r` 要求回答 `a[l] - a[r]`，如果无法根据线索推出答案，忽略这次操作

**算法分析**
给出条件 $$a_l - a_r = x$$，相当于 $$(l, r)$$ 连一条权值为$$x$$的边
对于询问 $$a_l - a_r$$ 能否推出答案，相当于询问 $$l, r$$ 在不在一个**连通块**中

> 先考虑怎么用并查集来维护信息？

并查集中，$$x$$ 的父亲设为 $$f(x)$$，我们记 $$w(x) = a(x) - a(f(x))$$
这样，对于查询操作 `a[l] - a[r]`，如果我们找到 $$f(l) = f(r) = p$$
```math
\displaystyle
\begin{cases}
w(l) = a(l) - a(f(l)) = a(l) - a(p) \\
w(r) = a(r) - a(p)
\end{cases}
\\
\quad
\\
\Rightarrow \quad a_l - a_r = w(l) - w(r)
```

> 按秩压缩的时候如何维护？

在并查集路径压缩的时候考虑值会如何变化？
一般来说，`find(x)`的时候，先把原来的 `f(x)` 缓存下来，令 `p = f(x)`
然后执行**路径压缩**`find(p)`，假设路径压缩后 `f(p) = q`，原先维护的是 $$w(x)$$
路径压缩后，$$w(x) \to w'(x)$$，那么它具体是多少呢？
```math
\displaystyle
w(x) = a(x) - a(p) \\
w'(x) = a(x) - a(q) \\
```
另外我们有  $$w(p) = a(p) - a(q)$$，所以

$$w'(x) = (w(x) + a(p)) - (a(p) - w(p)) = w(x) + w(p)$$

也就是说，我们需要另 `w[x] = w[x] + w[p]`
最后令 `f[x] = f[p]`，将 $$x$$ 的路径和 $$p$$ 的路径压缩到一起

> 并查集如何维护修改操作？

执行 `1 l r x` 的时候，需要把 `l` 和 `r` 合并在一起，也就是说，执行
`f( f(l) ) = f(r)`，那么我们要**修改**`w[ f(l) ] = a[ f(l) ] - a[ f(r) ]`
而实际上我们不知道 `a[  ]`，我们已有信息是 `a[l] - a[r] = x`，另外
```math
w(l) = a(l) - a(f(l)) \\
w(r) = a(r) - a(f(r))
```
两式相减，得到 $$\displaystyle w(l) - w(r) = a(l) - a(r) - \left(a(f(l)) - a(f(r)) \right)$$
即 $$w(l) - w(r) = x - (a(f(l)) - a(f(r)))$$

从而，`w[ f(l) ] = a[ f(l) ] - a[ f(r) ] = x + w(r) - w(l)`

### 算法实现
```bash
template<class T>
struct DSU {
    int n;
    vector<T> pa, sz, w;
    DSU(int _n = 1) : n(_n), w(n+1, 0) {
        pa.resize(n+1), iota(pa.begin(), pa.end(), 0);
        sz.resize(n+1), fill(sz.begin(), sz.end(), 1);
    }

T findpa(T x) {
        return pa[x] == x ? x : (pa[x] = findpa(pa[x]));
    }
    T dfind(T x) {
        T &p = pa[x];
        if (p == x) return x;

T r = dfind(p);
        w[x] = w[x] + w[p];
        return p = r;
    }
    T setsize(T x) {
        T r = findpa(x);
        return sz[r];
    }

bool same(int x, int y) {
        x = dfind(x), y = dfind(y);
        return x == y;
    }

void connect(int l, int r, ll x) {
        int pl = pa[l], pr = pa[r];
        // w[ pl ] = w[r] - w[l] + x

w[pl] = w[r] - w[l] + x;
        pa[pl] = pr;
    }
};
```

上一篇：树状数组，线段树一些常见的问题下一篇：莫队算法与根号分治

看完文章有啥想法