wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数据结构

线段树

线段树单点修改

线段树区间修改

动态开点线段树

线段树的合并（一）

线段树的分裂

可持久化线段树

树链剖分

平衡树

FHQ-Treap

珂朵莉树

分块

位分块

根号分治

虚树

[[ item.c ]]

线段树的分裂

## 一些问题回顾
### Promotion Counting P
**[Promotion Counting P](https://www.luogu.com.cn/problem/P3605)**
**问题描述**
给定一棵树，每个点有点权，求每个点的子树中有多少个点的点权，大于这个点的点权

**算法分析**
标准的线段树合并
1）离散化所有的点
2）对于叶子结点，权值为`wgt[v]`，`change(root[v], wgt[v], 1)`
3）对于$$u$$，将子树合并到`root[u]`中，并在`root[u]`中区间查询`[wgt[u]...m]`的**区间和**

## 线段树分裂
![](/media/content_img/segtreeSplit01.png)

## 线段树分裂的一些问题
### 模版-线段树分裂
**[P5494 【模板】线段树分裂](https://www.luogu.com.cn/problem/P5494)**
**问题描述**
给定一个可重集$$a$$，编号是`1`，支持以下操作
```bash
0 p x y，将可重集 p 中 [x, y] 区间内的值移动到一个新的可重集中，新的可重集编号从 2 开始递增
1 p t，将可重集 t 中的数放入可重集 p，然后清空可重集 t
2 p x q，在 p 这个可重集中加入 x 个数字 q
3 p x y，查询可重集 p 中 [x, y] 区间内值的个数
4 p k，查询 p 这个可重集中第 k 小的数，不存在输出 -1
```
**算法分析**
![](/media/content_img/segtreeSplit2.png)

维护一个`vector<int> roots`来存储所有可重集对应的线段树根节点
（初始化 roots.assign(2, 0)，因为编号从 $1$ 开始且新集合从 $2$ 递增）

根据`a`初始序列，建立一棵初始化的**动态开点线段树**

> 维护操作如下

**操作 `0 (0 p x y)`：分裂**
直接调用并压入新根节点，`roots.push_back( tree.split(roots[p], x, y) )`

**操作`1 (1 p t)`: 合并**
没什么好说的，`roots[p] = tree.merge(roots[p], roots[t]), then roots[t] = 0`

**操作 `2 (2 p x q)`: 插入**
`tree.change(roots[p], q, Info{x})`，注意是针对权值线段树

**操作`3 (3 p x y)`: 区间查询**
`tree.rangeQuery(roots[p], x, y).cnt`

**操作`4 (4 p k)`: 第 K 小**
`tree.findKth(roots[p], k)`

### 排序
**[HEOI2016/TJOI2016 排序](https://www.luogu.com.cn/problem/P2824)**
**问题描述**
给定一个`1-n`的排列，进行`m`次操作
```bash
0 l r 表示将区间 [l, r] 的数升序排序
1 l r 表示将区间 [l, r] 的数降序排序
```
若干次操作之后，询问第$$q$$位置上的数是多少

**算法分析**
基本思想，考虑**权值线段树**，如果我们考虑区间`[l...r]`，对每个这样的区间**开一棵权值线段树**
那么`root[区间id]`维护了这个区间内到底包含哪些数字

那么题目中将`[l, r]`排序，这样的操作，相当于将这个区间内所有**小的，零散的线段树**合并成一棵大的线段树`tr`
合并完，`tr`维护了**到底包含哪些权值**，这些权值都是天然有序的（在叶子节点）

> 那么，排序的操作，相当于将`[l...r]`区间推平，将这些点对应的线段树的根都变成`idx`
区间推平，不难想到珂朵莉树`ODT`

![](/media/content_img/TJOJ2016.png)

> 最后，怎么查询呢？

查询下标是`q`，那么在`珂朵莉树 ODT`上找到包含`q`的区间`[l, r]`
这个区间所对应的线段树的根是`rt`，另外这个区间是有序的
要查的是第几个数呢？`K = q - l + 1`

如果区间是升序的，那么答案就是`Kth`个数
否则，从最大往最小数`K`个，也就是从最小往最大数`tot - K + 1`个
用线段树的`findKth`方法就可以

#### 算法实现
```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

vector<int> a(n+1, 0);
    for (auto &x : a | views::drop(1)) cin >> x;

set<Node> odt;
    DynamicSegtree<Info> tr(n);

for (int i = 1; i <= n; i++) {
        auto x = a[i];

int root = 0;
        tr.change(root, x, Info{1});
        odt.insert(Node{i, i, 0, root});
    }
    // [l, r, op, root]

auto split = [&](int x) {
        // [l, r] -> [l, x-1] + [x, r], x 是下标，返回指向 [x, r] 的迭代器
        auto it = odt.lower_bound(Node{x, 0, 0, 0});

if (it != odt.end() && it->l == x) return it;
        --it;

// it=[l, r] --> [l, x-1] + [x, r]
        auto [l, r, op, root] = *it;

odt.erase(it);

int ls = 0, rs = 0;
        int K = x - l, tot = r - l + 1;
        // segtree split
        if (op == 0) {
            rs = tr.splitK(root, K);
            ls = root;
        }
        else {
            ls = tr.splitK(root, tot - K);
            rs = root;
        }
        
        odt.insert(Node(l, x-1, op, ls));
        return odt.insert(Node(x, r, op, rs)).first;
    };

auto assign = [&](int l, int r, int op) {
        // [l, r] -> 赋值为 v
        auto itr = split(r+1), itl = split(l);

int RT = 0;
        for (auto it = itl; it != itr; it++) {
            auto root = it->rt;
            RT = tr.merge(RT, root, 1, tr.n);
        }

odt.erase(itl, itr);

odt.insert(Node{l, r, op, RT});
    };

for (int i = 0; i < m; i++) {
        int op, l, r;
        cin >> op >> l >> r;
        assign(l, r, op);
    }

int q;
    cin >> q;

auto it = odt.upper_bound(Node{q, 0, 0, 0});
    it--;

auto [l, r, op, rt] = *it;
    int K = q - l + 1;

if (op == 1) {
        int tot = r - l + 1;
        K = tot - K + 1;
    }

int ans = tr.findKth(rt, K);
    cout << ans << "\n";
}
```
## 线段树分裂的算法实现
```bash
template<class Info>
class DynamicSegtree {
public:
    // 将 [ql, qr] 范围内的数据，分裂到一个新树中
    int split(int &p, int l, int r, int ql, int qr) {
        if (!p) return 0;

// 如果当前区间被 [ql, qr] 完全包含，直接将子树移交给新树
        if (ql <= l and r <= qr) {
            int q = p;
            p = 0;
            return q;
        }
        
        int mid = (l + r) >> 1;
        int pls = t[p].ls, prs = t[p].rs;
        int qls = 0, qrs = 0;

// 按需分裂左右子树
        if (ql <= mid) qls = split(pls, l, mid, ql, qr);
        if (qr > mid) qrs = split(prs, mid + 1, r, ql, qr);

// 更新原树
        t[p].ls = pls, t[p].rs = prs;
        pull(p);

int q = 0;
        // 新树接管，只有在左右儿子真正分裂出数据的时候才接管
        if (qls or qrs) {
            q = New();
            t[q].ls = qls, t[q].rs = qrs;
            pull(q);
        }

// 都做完之后，p 被分裂，如果被分类成空的，清空指针
        if (t[p].ls == 0 and t[p].rs == 0 and t[p].info == Info{}) {
            recycle(p);
            p = 0;
        }

return q;
    }

// 按前 k 小的数量分裂
    // p 树保留最小的 k 个数，返回剥离出的包含剩余数字的新树的根
    int splitK(int &p, int l, int r, i64 K) {
        if (!p) return 0;

if (K == 0) {
            // p 全部被分走，自身不留
            int q = p;
            p = 0;
            return q;
        }

// 如果 K 包含了 p 中所有的数，不用分裂
        if (K == t[p].info.cnt) return 0;

int q = New();
        int mid = (l + r) >> 1;

i64 leftCnt = t[t[p].ls].info.cnt;

if (K <= leftCnt) {
            // 右边全部给 q，左边可能要拿出一部分，给 q 的左子树
            t[q].rs = t[p].rs, t[p].rs = 0;
            t[q].ls = splitK(t[p].ls, l, mid, K);
        }
        else {
            // 左子树必须保留在 p 中，右子树从 p 中去拿
            t[q].ls = 0;
            t[q].rs = splitK(t[p].rs, mid + 1, r, K - leftCnt);
        }
        pull(p);
        pull(q);

if (!t[p].ls and !t[p].rs and t[p].info == Info{}) {
            recycle(p);
            p = 0;
        }

return q;
    }

};
```

看完文章有啥想法

算法小站

wiki 主题

数据结构

线段树的分裂

目录