数据结构Part 2

这玩意会持续更新，因为太多了。

0.定义

线段树是一种可以很方便的维护区间信息的 DS，是一种Leafy Tree。

线段树的一个结点是维护的原序列的一段区间的信息。具体结构是一棵完全二叉树，若一个结点维护的是 $[l,r]$ 的信息，设 $m = \lfloor \frac{l + r}{2} \rfloor$ 则根结点的左儿子维护的就是 $[l,m]$ ，右儿子维护的是 $[m + 1,r]$ 的信息。

结点需要用 pushup 操作来合并信息，由于是分两块计算，所以维护的东西必须有结合律，更准确的说，维护的信息必须是个幺半群，即需要有结合律，有单位元。

一般设根结点的下标为 rt，则左子树的下标为 rt * 2 = rt << 1，右子树的下标为 rt * 2 + 1 = rt << 1 | 1。

结构体如下：

1
struct Rukkhadevata
2
{
3
    int l,r;
4
    Info...;
5
    // Lazytag...;
6
}tree[MAXN << 2];
7
inline void pushup(int rt)
8
{
9
    tree[rt].info = merge(tree[rt << 1].info,tree[rt << 1 | 1].info);
10
}
11
inline void pushdown(int rt)
12
{
13
    if(available(tree[rt].laz))
14
    {
15
        Operation(rt << 1,tree[rt].laz);
16
        Operation(rt << 1 | 1,tree[rt].laz);
17
        reset(tree[rt].laz);
18
    }
19
}

需要注意，这种堆式存储要开 4 倍空间。

1.操作

建树

我们递归的处理每个区间，对每个结点分配边界，如果是叶子结点就分配信息，在回溯的时候执行 pushup 合并信息。

1
inline void build(int l,int r,int rt)
2
{
3
    tree[rt].l = l,tree[rt].r = r;
4
    if(l == r)
5
    {
6
        tree[rt].info = origin[l];
7
        return ;
8
    }
9
    int mid = (l + r) >> 1;
10
    build(l,mid,rt << 1);
11
    build(mid + 1,r,rt << 1 | 1);
12
    pushup(rt);
13
}

区间修改类

我们需要维护一个 lazytag，具体的，就是直接给一个子树的根结点打标记，不直接修改，等需要查询子区间的时候再 pushdown 下去。不同的 lazytag 间可能相互有影响，需要根据维护的信息适时下放标记。

然后我们需要递归区间，分三种情况：

修改区间完全包含现区间，则直接打标记。
修改区间和现区间的左半部分有交集，就递归向左子树走。
修改区间和现区间的右半部分有交集，就递归向右子树走。

模板代码如下：

1
inline void modify(int l,int r,int rt,int val)
2
{
3
    if(l <= tree[rt].l && r >= tree[rt].r)
4
    {
5
        Operation(rt,val);
6
        return ;
7
    }
8
    // pushdown(rt);
9
    int mid = (tree[rt].l + tree[rt].r) >> 1;
10
    if(l <= mid)
11
        modify(l,r,rt << 1,val);
12
    if(r > mid)
13
        modify(l,r,rt << 1 | 1,val);
14
    pushup(rt);
15
}

区间查询类

还是一样的，注意准备前往子结点的时候需要下传标记。

1
inline int query(int l,int r,int rt)
2
{
3
    if(l <= tree[rt].l && r >= tree[rt].r)
4
        return tree[rt].val;
5
    // pushdown(rt);
6
    int mid = (tree[rt].l + tree[rt].r) >> 1,res = identity();
7
    if(l <= mid)
8
        Operation(res,query(l,r,rt << 1));
9
    if(r > mid)
10
        Operation(res,query(l,r,rt << 1 | 1));
11
    return res;
12
}

2.权值线段树

类似权值树状数组，可以查询全局 $k$ 小值，查询排名等，在某些时候可以代替平衡树。

$k$ 小值可以线段树上二分，排名就是直接一个前缀和。

3.动态开点线段树

有的时候，题目不允许我们使用堆式存储开线段树，又不能离散化的时候，我们就可以使用动态开点的方式。具体的，就是刚开始只有一个管辖 $[1,n]$ 的根结点，等需要用的时候才开这个点。

因为每次操作最多创建 $\Omicron(\log n)$ 个结点，所以最后的空间复杂度可以从 $T(4n)$ 优化到 $\Omicron(q \log n)$ 。

结构体会有些变化：

1
struct Rukkhadevata
2
{
3
    int ls,rs;
4
    int l,r; // 其实可以不计
5
    Info...;
6
    // Lazytag...;
7
}tree[MAXQ * LOGN];
8
#define lson tree[rt].ls
9
#define rson tree[rt].rs

需要多加一个 newNode 操作，你也可以选择不加。~~这怎么一股平衡树味~~

1
inline int newNode(int l,int r,int val)
2
{
3
    ++cnt;
4
    tree[cnt].l = l,tree[cnt].r = r,tree[cnt].val = val,tree[cnt].ls = tree[cnt].rs = 0;
5
    return cnt;
6
}

因为不需要初始化所有结点，所以我们可以省略建树操作。相应的，别的操作也需要一些修改。

1
inline void pushup(int rt)
2
{
3
    tree[rt].val = merge(tree[lson].val,tree[rson].val);
4
}
5
inline void pushdown(int rt)
6
{
7
    if(tree[rt].laz)
8
    {
9
        if(lson)
10
            Operation(lson,tree[rt].laz);
11
        if(rson)
12
            Operation(rson,tree[rt].laz);
13
        reset(tree[rt].laz);
14
    }
15
}
16
inline void modify(int &rt,int l,int r,int L,int R,int val)
17
{
18
    if(!rt)
19
        rt = newNode(l,r,val);
20
    if(L <= l && R >= r)
21
    {
22
        Operation(rt,val);
23
        return ;
24
    }
25
    int mid = (l + r) >> 1;
26
    if(L <= mid)
27
        modify(lson,l,mid,L,R,val);
28
    if(R > mid)
29
        modify(rson,mid + 1,r,L,R,val);
30
    pushup(rt);
31
}
32
inline int query(int rt,int l,int r,int L,int R)
33
{
34
    if(!rt)
35
        return 0;
36
    if(L <= l && R >= r)
37
        return tree[rt].val;
38
    int mid = (l + r) >> 1,res = identity();
39
    if(L <= mid)
40
        Operation(res,query(lson,l,mid,L,R));
41
    if(R > mid)
42
        Operation(res,query(rson,mid + 1,r,L,R));
43
    return res;
44
}

4.势能线段树

lazytag 的需求就是可以合并，并且可以更新子结点。但是有的操作就不满足，比如区间开根。

但是，我们惊奇的发现，区间开根对 $0$ 和 $1$ 没有贡献。所以，我们可以维护区间最大值，若最大值 $\le 1$ 则直接返回，否则接着向下走。

也因此，我们可以维护区间历史最值，区间取 min/max 等操作，而这就是吉司机线段树。

5.李超线段树

~~这是真“线段”树~~

这个线段树是用来维护线段的最高/最低点的，并且可以支持插入线段。

每个结点维护的是一段区间内的最优线段，就是这个线段在区间中点处的 $y$ 值是最大的线段。

这个东西的核心就在分类讨论，具体如下：

新线段完全覆盖老线段，则直接修改，返回。
老线段完全覆盖新线段，则直接返回。
刚好交于中点，归于新线段不如老线段。
这写不下，往下看。

如果新线段 $f$ 优于老线段 $g$ ，就先交换一下，我们考虑中点处 $f$ 不如 $g$ 优的情况。

若左端点 $f$ 优于 $g$ ，则交点会在左区间，前往左儿子处理。
若右端点 $f$ 优于 $g$ ，则交点会在右区间，前往右儿子处理。
如果都不优，则直接返回。

或者还有一种比较斜率的办法：

若 $g$ 的斜率小于 $f$ ，则比较中点的 $y$ 坐标，若 $g$ 小于 $f$ 则前往右儿子更新 $g$ ，否则前往左儿子更新 $f$ 。
若 $g$ 的斜率大于 $f$ ，且中点坐标 $g$ 小于 $f$ ，则前往左儿子更新 $g$ ，否则前右儿子更新 $f$ 。
斜率一致那比较截距， $f$ 优于 $g$ 就更新。

查询就很简单，枚举所有可能包含 $pos$ 的线段，然后取极值。

模板代码如下（不含线段拆分，给斜率优化用的那种）：

1
namespace LiChaoSGT
2
{
3
    struct Rukkhadevata
4
    {
5
        int ls,rs,seg;
6
    }tree[MAXN];
7
    int k[MAXN],b[MAXN];
8
    inline int F(int id,int x)
9
    {return k[id] * x + b[id];}
10
    int cnt,root;
11
    inline void insert(int &rt,int l,int r,int S)
12
    {
13
        if(!rt)
14
            tree[rt = ++cnt].seg = S;
15
        else
16
        {
17
            if(l == r)
18
            {
19
                if(F(S,l) < F(tree[rt].seg,l))
20
                    tree[rt].seg = S;
21
                return ;
22
            }
23
            int mid = (l + r) >> 1;
24
            if(F(S,mid) < F(tree[rt].seg,mid))
25
                swap(S,tree[rt].seg);
26
            if(F(S,l) < F(tree[rt].seg,l))
27
                insert(tree[rt].ls,l,mid,S);
28
            if(F(S,r) < F(tree[rt].seg,r))
29
                insert(tree[rt].rs,mid + 1,r,S);
30
        }
31
    }
32
    inline int query(int rt,int l,int r,int p)
33
    {
34
        if(!rt)
35
            return LONG_LONG_MAX;
36
        if(l == r)
37
            return F(tree[rt].seg,p);
38
        int mid = (l + r) >> 1;
39
        return min(F(tree[rt].seg,p),(p <= mid) ? query(tree[rt].ls,l,mid,p) : query(tree[rt].rs,mid + 1,r,p));
40
    }
41
}

6.可持久化

这玩意分两种，但维护都差不多（我感觉可持久化数据结构的变化都挺像的）

可持久化线段树

我喜欢叫可持久化数组。

我们先思考，怎么暴力可持久化。

这不简单，直接复制

是，但是空间立刻爆炸。

我们发现，每次修改，最多会访问 $\log n$ 个结点，如下图：

所以，我们可以考虑只将这一条链复制下来，和原来的线段树共用一些结点，对每个版本，把根结点存下来就好了。

其实懂了以后就不难写出代码，这里贴一个模板题↗的：

1
namespace PersistentSGT
2
{
3
    struct Nahida
4
    {
5
        int ls,rs,val;
6
    }tree[MAXN << 5];
7
    int cnt,root[MAXN];
8
    inline int newNode(int node)
9
    {
10
        ++cnt;
11
        tree[cnt] = tree[node];
12
        return cnt;
13
    }
14
    inline int build(int rt,int l,int r)
15
    {
16
        rt = ++cnt;
17
        if(l == r)
18
        {
19
            tree[rt].val = a[l];
20
            return cnt;
21
        }
22
        int mid = (l + r) >> 1;
23
        tree[rt].ls = build(tree[rt].ls,l,mid);
24
        tree[rt].rs = build(tree[rt].rs,mid + 1,r);
25
        return rt;
26
    }
27
    inline int update(int rt,int l,int r,int pos,int val)
28
    {
29
        rt = newNode(rt);
30
        if(l == r)
31
            tree[rt].val = val;
32
        else
33
        {
34
            int mid = (l + r) >> 1;
35
            if(pos <= mid)
36
                tree[rt].ls = update(tree[rt].ls,l,mid,pos,val);
37
            else
38
                tree[rt].rs = update(tree[rt].rs,mid + 1,r,pos,val);
39
        }
40
        return rt;
41
    }
42
    inline int query(int rt,int l,int r,int pos)
43
    {
44
        if(l == r)
45
            return tree[rt].val;
46
        int mid = (l + r) >> 1;
47
        if(pos <= mid)
48
            return query(tree[rt].ls,l,mid,pos);
49
        else
50
            return query(tree[rt].rs,mid + 1,r,pos);
51
    }
52
}

可持久化权值线段树

也叫主席树。

就是把权值线段树可持久化的产物，可以拿来解决区间 k 小值。

具体来说，先离散化，然后从左到右依次添加每个值，并且每次添加完后保存根结点，这样我们就得出了所有 $[1,i]$ 的线段树，这个时候，我们可以运用差分的思想，用 $[1,r]$ 的线段树减去 $[1,l - 1]$ 的线段树（每个结点对应相减），就得到了 $[l,r]$ 的线段树。然后正常权值线段树查询 $k$ 小值就行了。

应用

可持久化线段树可以让很多基于数组的数据结构变得可持久化，还有就是维护每次变化很小并且需要访问历史版本的信息。

主席树用处就多了去了，外层的前缀和/差分可以看作一层数据结构，因此主席树维护的是静态的二维信息，你可以把外面的换成树状数组，就可以维护动态的了。

同时，这个启发我们，权值线段树是可以“差分”的。

虽然说不强制在线可以被整体二分/CDQ 分治等离线算法吊着打，~~但是我就喜欢 DS~~。

注意

但凡是可持久化的题空间一般不会太小，除非毒瘤出题人。所以我们可以大胆一点，直接开 $32$ 倍空间。

并且这个东西需要共用结点，不能写堆式存储，必须写动态开点的写法。

类似的前缀和思想在可持久化字典树也有体现。

7.标记永久化

有的时候，上面的上传/下传标记不再适用，比如写主席树和树套树的时候。

这个时候，我们干脆直接不下传标记，直接在访问某个结点的时候累加所有标记就行了。

修改会有些不同：如果操作区间完全覆盖现在的区间，则只打标记不改值，否则修改值。

可以看下面的模板，实现了区间加法：

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4

5
constexpr int MAXN = 1e5 + 24;
6
struct Rukkhadevata
7
{
8
    int val,laz;
9
}tree[MAXN << 2];
10
int a[MAXN];
11
inline void build(int l,int r,int rt)
12
{
13
    if(l == r)
14
    {
15
        tree[rt].val = a[l];
16
        return ;
17
    }
18
    int mid = (l + r) >> 1;
19
    build(l,mid,rt << 1);
20
    build(mid + 1,r,rt << 1 | 1);
21
    tree[rt].val = tree[rt << 1].val + tree[rt << 1 | 1].val; // 建树需要 pushup 一下
22
}
23
inline void modify(int rt,int l,int r,int L,int R,int val)
24
{
25
    if(L <= l && R >= r)
26
    {
27
        tree[rt].laz += val; // 完全覆盖只打标记
28
        return ;
29
    }
30
    tree[rt].val += (R - L + 1) * val; // 否则修改值
31
    int mid = (l + r) >> 1;
32
    if(R <= mid)
33
        modify(rt << 1,l,mid,L,R,val);
34
    else if(L > mid)
35
        modify(rt << 1 | 1,mid + 1,r,L,R,val);
36
    else
37
        modify(rt << 1,l,mid,L,mid,val),modify(rt << 1 | 1,mid + 1,r,mid + 1,R,val);
38
}
39
inline int query(int rt,int l,int r,int L,int R)
40
{
41
    int res = tree[rt].laz * (R - L + 1); // 累加标记的贡献
42
    if(L <= l && R >= r)
43
        return tree[rt].val + res;
44
    int mid = (l + r) >> 1;
45
    if(R <= mid)
46
        res += query(rt << 1,l,mid,L,R);
47
    else if(L > mid)
48
        res += query(rt << 1 | 1,mid + 1,r,L,R);
49
    else
50
        res += query(rt << 1,l,mid,L,mid) + query(rt << 1 | 1,mid + 1,r,mid + 1,R);
51
    return res;
52
}
53
int n,m,opt,l,r,v;
54
signed main()
55
{
56
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
57
    cin >> n >> m;
58
    for(int i = 1;i <= n;i++)
59
        cin >> a[i];
60
    build(1,n,1);
61
    for(int i = 1;i <= m;i++)
62
    {
63
        cin >> opt >> l >> r;
64
        if(opt == 1)
65
        {
66
            cin >> v;
67
            modify(1,1,n,l,r,v);
68
        }
69
        else
70
            cout << query(1,1,n,l,r) << "\n";
71
    }
72
}

8.线段树维护矩阵乘法

前面我们说了，线段树维护的信息实质上是一个幺半群。

我们又发现，矩阵乘法这东西既有结合律还有单位元，所以可以放到线段树上维护。

但直接维护，显然没有什么意义，除非有毒瘤出题人出这个可爱题。

我们回过头去看P3373 线段树2↗，发现我们需要维护两个 lazytag，太烦了。

这个时候，我们维护的矩阵乘法就有用了。

我们不难发现，我们可以~~多此一举的~~做下面的操作：

$a \gets a + k \Rightarrow \begin{bmatrix} a \end{bmatrix} \gets \begin{bmatrix} a \end{bmatrix} + \begin{bmatrix} k \end{bmatrix}$

然后，对于线段树的每个结点，我们考虑维护一个矩阵 $\begin{bmatrix} val & len \end{bmatrix}$ ，其中 $val$ 表示这个结点的值， $len$ 表示该区间长度。

我们不难构造出这个转移矩阵 $\begin{bmatrix} 1 & 0 \\ k & 1 \end{bmatrix}$ ，使得我们可以将加法操作写成 $\begin{bmatrix} val & len \end{bmatrix} \gets \begin{bmatrix} val & len \end{bmatrix} \begin{bmatrix} 1 & 0 \\ k & 1 \end{bmatrix}$ 。

同理，我们可以构造出一个乘法的转移矩阵 $\begin{bmatrix} k & 0 \\ 0 & 1 \end{bmatrix}$ 。

这个时候，我们矩阵乘法的结合律就发挥作用了。我们只用维护一个矩阵作为 lazytag，就可以了。

但是，它的作用远不止于此。

我们可以定义广义矩阵乘法如下：

C = A * B C _ {i,j} = \max A _ {i,k} + B _ {k,j}

懒得证明了，反正它有结合律，还有单位元为 $\begin{bmatrix} 0 & -\infty & \ldots & -\infty -\infty & 0 & \ldots & -\infty \vdots & \vdots & \ddots & \vdots -\infty & -\infty & \ldots & 0 \end{bmatrix}$ 。

我们再看这道题：P4314 CPU 监控↗。

我们可以将信息这么维护： $\begin{bmatrix} a _ i & b _ i & 0 \end{bmatrix}$ ， $a _ i$ 表示这个位置的值， $b _ i$ 表示历史最值。pushup 就是维护区间最值， $a _ i \gets \max \{ a _ {ls _ i},a _ {rs _ i} \},b _ i \gets \max \{ b _ {ls _ i},b _ {rs _ i} \}$ 。

因为 $\begin{bmatrix} a _ i & b _ i & 0 \end{bmatrix} \to \begin{bmatrix} a _ i + k & \max \{b _ i,a _ i + k\} & 0 \end{bmatrix}$ ，加法矩阵是长这样的： $\begin{bmatrix} k & k & -\infty \\ -\infty & 0 & -\infty \\ -\infty & -\infty & 0 \end{bmatrix}$ ； $\begin{bmatrix} a _ i & b _ i & 0 \end{bmatrix} \to \begin{bmatrix} k & \max \{b _ i,k\} & 0 \end{bmatrix}$ ，覆盖矩阵是 $\begin{bmatrix} -\infty & -\infty & -\infty \\ -\infty & 0 & -\infty \\ k & k & 0 \end{bmatrix}$ 。

然后就可以方便的维护这些操作了。

~~但是两个大常数的东西在一起真的不会 T 吗~~

这个东西可能需要一些卡常，可以用标记永久化降低常数。

动态 DP 也是基于这个原理，可以用数据结构维护。

9.吉司机线段树/Segment Beats

可以维护区间取最值操作/区间历史最值查询。

先上一道例题

给你一个序列 $a _ i$ ，维护以下操作
$\forall i \in [l,r],a _ i \gets \min (a _ i,x)$
输出 $\max \{ a _ i \},i \in [l,r]$
输出 $\sum _ {i = l} ^ r a _ i$

我们发现取 $\min$ 很不好维护，考虑转化。

我们维护以下几个值：

区间内最大值 $max$ ，区间内严格次大值 $smx$ ，区间和 $sum$ ，区间内最大值个数 $cnt$ 。

再维护以下 lazytag：

加法标记 $lazsum$ ，取 $\min$ 标记 $lazmin$

我们考虑将取 $\min$ 操作转化为加减法。

对于操作 $1$ ，做以下分类讨论：

若 $x \ge max$ ，则操作对这个区间及子区间无效，直接返回（和上面的势能线段树类似）。
若 $smx \lt x \le max$ ，操作会对所有的 $max$ 生效，对区间和产生 $(x - max)cnt$ 的贡献，同时打标记。
否则，暴力向下。

这个可以通过势能分析法证明，复杂度是 $\Omicron(n \log n)$ 的。

有些题会让你同时维护六个操作（区间 $\min / \max / \sum$ 修改/查询），这种出生题码量会非常大，同时需要大力分讨。

所以吉司机线段树一个 pushup 有 $40$ 多行挺正常的。

这里附一份完整代码。

BZOJ 4695，上面的六个操作的

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4

5
constexpr int MAXN = 5e5 + 5,inf = 1e18;
6
int n,m,opt,l,r,x,a[MAXN];
7
struct Rukkhadevata
8
{
9
    int max,min,smx,smn,mxCnt,mnCnt,sum;
10
    int lazmx,lazmn,lazsm;
11
}tree[MAXN << 2];
12
inline void pushup(int rt)
13
{
14
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
15
    if(tree[rt << 1].max == tree[rt << 1 | 1].max)
16
    {
17
        tree[rt].max = tree[rt << 1].max;
18
        tree[rt].smx = max(tree[rt << 1].smx,tree[rt << 1 | 1].smx);
19
        tree[rt].mxCnt = tree[rt << 1].mxCnt + tree[rt << 1 | 1].mxCnt;
20
    }
21
    else if(tree[rt << 1].max > tree[rt << 1 | 1].max)
22
    {
23
        tree[rt].max = tree[rt << 1].max;
24
        tree[rt].smx = max(tree[rt << 1].smx,tree[rt << 1 | 1].max);
25
        tree[rt].mxCnt = tree[rt << 1].mxCnt;
26
    }
27
    else
28
    {
29
        tree[rt].max = tree[rt << 1 | 1].max;
30
        tree[rt].smx = max(tree[rt << 1].max,tree[rt << 1 | 1].smx);
31
        tree[rt].mxCnt = tree[rt << 1 | 1].mxCnt;
32
    }
33
    if(tree[rt << 1].min == tree[rt << 1 | 1].min)
34
    {
35
        tree[rt].min = tree[rt << 1].min;
36
        tree[rt].smn = min(tree[rt << 1].smn,tree[rt << 1 | 1].smn);
37
        tree[rt].mnCnt = tree[rt << 1].mnCnt + tree[rt << 1 | 1].mnCnt;
38
    }
39
    else if(tree[rt << 1].min < tree[rt << 1 | 1].min)
40
    {
41
        tree[rt].min = tree[rt << 1].min;
42
        tree[rt].smn = min(tree[rt << 1].smn,tree[rt << 1 | 1].min);
43
        tree[rt].mnCnt = tree[rt << 1].mnCnt;
44
    }
45
    else
46
    {
47
        tree[rt].min = tree[rt << 1 | 1].min;
48
        tree[rt].smn = min(tree[rt << 1].min,tree[rt << 1 | 1].smn);
49
        tree[rt].mnCnt = tree[rt << 1 | 1].mnCnt;
50
    }
51
}
52
inline void build(int l,int r,int rt)
53
{
54
    tree[rt].lazmn = inf,tree[rt].lazmx = -inf;
55
    if(l == r)
56
    {
57
        tree[rt].sum = tree[rt].max = tree[rt].min = a[l];
58
        tree[rt].smx = -inf,tree[rt].smn = inf;
59
        tree[rt].mxCnt = tree[rt].mnCnt = 1;
60
        return ;
61
    }
62
    int mid = (l + r) >> 1;
63
    build(l,mid,rt << 1);
64
    build(mid + 1,r,rt << 1 | 1);
65
    pushup(rt);
66
}
67
inline void updateSum(int rt,int val,int l,int r)
68
{
69
    tree[rt].sum += (r - l + 1ll) * val;
70
    tree[rt].max += val,tree[rt].min += val;
71
    if(tree[rt].lazmn != inf)
72
        tree[rt].lazmn += val;
73
    if(tree[rt].lazmx != -inf)
74
        tree[rt].lazmx += val;
75
    if(tree[rt].smn != inf)
76
        tree[rt].smn += val;
77
    if(tree[rt].smx != -inf)
78
        tree[rt].smx += val;
79
    tree[rt].lazsm += val;
80
}
81
inline void updateMin(int rt,int val)
82
{
83
    if(tree[rt].max <= val)
84
        return ;
85
    tree[rt].sum += (val - tree[rt].max) * tree[rt].mxCnt;
86
    if(tree[rt].smn == tree[rt].max)
87
        tree[rt].smn = val;
88
    if(tree[rt].min == tree[rt].max)
89
        tree[rt].min = val;
90
    tree[rt].lazmx = min(tree[rt].lazmx,val),tree[rt].max = val,tree[rt].lazmn = val;
91
}
92
inline void updateMax(int rt,int val)
93
{
94
    if(tree[rt].min > val)
95
        return ;
96
    tree[rt].sum += (val - tree[rt].min) * tree[rt].mnCnt;
97
    if(tree[rt].smx == tree[rt].min)
98
        tree[rt].smx = val;
99
    if(tree[rt].max == tree[rt].min)
100
        tree[rt].max = val;
101
    tree[rt].lazmn = max(tree[rt].lazmn,val),tree[rt].min = val,tree[rt].lazmx = val;
102
}
103
inline void pushdown(int rt,int l,int r)
104
{
105
    int mid = (l + r) >> 1;
106
    if(tree[rt].lazsm)
107
    {
108
        updateSum(rt << 1,tree[rt].lazsm,l,mid);
109
        updateSum(rt << 1 | 1,tree[rt].lazsm,mid + 1,r);
110
        tree[rt].lazsm = 0;
111
    }
112
    if(tree[rt].lazmx != -inf)
113
    {
114
        updateMax(rt << 1,tree[rt].lazmx);
115
        updateMax(rt << 1 | 1,tree[rt].lazmx);
116
        tree[rt].lazmx = -inf;
117
    }
118
    if(tree[rt].lazmn != inf)
119
    {
120
        updateMin(rt << 1,tree[rt].lazmn);
121
        updateMin(rt << 1 | 1,tree[rt].lazmn);
122
        tree[rt].lazmn = inf;
123
    }
124
}
125
inline void modifySum(int rt,int l,int r,int L,int R,int val)
126
{
127
    if(L <= l && R >= r)
128
        return updateSum(rt,val,l,r);
129
    pushdown(rt,l,r);
130
    int mid = (l + r) >> 1;
131
    if(L <= mid)
132
        modifySum(rt << 1,l,mid,L,R,val);
133
    if(R > mid)
134
        modifySum(rt << 1 | 1,mid + 1,r,L,R,val);
135
    pushup(rt);
136
}
137
inline void modifyMin(int rt,int l,int r,int L,int R,int val)
138
{
139
    if(tree[rt].max <= val)
140
        return ;
141
    if(L <= l && R >= r && tree[rt].smx < val)
142
        return updateMin(rt,val);
143
    pushdown(rt,l,r);
144
    int mid = (l + r) >> 1;
145
    if(L <= mid)
146
        modifyMin(rt << 1,l,mid,L,R,val);
147
    if(R > mid)
148
        modifyMin(rt << 1 | 1,mid + 1,r,L,R,val);
149
    pushup(rt);
150
}
151
inline void modifyMax(int rt,int l,int r,int L,int R,int val)
152
{
153
    if(tree[rt].min >= val)
154
        return ;
155
    if(L <= l && R >= r && tree[rt].smn > val)
156
        return updateMax(rt,val);
157
    pushdown(rt,l,r);
158
    int mid = (l + r) >> 1;
159
    if(L <= mid)
160
        modifyMax(rt << 1,l,mid,L,R,val);
161
    if(R > mid)
162
        modifyMax(rt << 1 | 1,mid + 1,r,L,R,val);
163
    pushup(rt);
164
}
165
inline int querySum(int rt,int l,int r,int L,int R)
166
{
167
    if(L <= l && R >= r)
168
        return tree[rt].sum;
169
    pushdown(rt,l,r);
170
    int mid = (l + r) >> 1,res = 0;
171
    if(L <= mid)
172
        res += querySum(rt << 1,l,mid,L,R);
173
    if(R > mid)
174
        res += querySum(rt << 1 | 1,mid + 1,r,L,R);
175
    return res;
176
}
177
inline int queryMax(int rt,int l,int r,int L,int R)
178
{
179
    if(L <= l && R >= r)
180
        return tree[rt].max;
181
    pushdown(rt,l,r);
182
    int mid = (l + r) >> 1,res = -inf;
183
    if(L <= mid)
184
        res = max(res,queryMax(rt << 1,l,mid,L,R));
185
    if(R > mid)
186
        res= max(res,queryMax(rt << 1 | 1,mid + 1,r,L,R));
187
    return res;
188
}
189
inline int queryMin(int rt,int l,int r,int L,int R)
190
{
191
    if(L <= l && R >= r)
192
        return tree[rt].min;
193
    pushdown(rt,l,r);
194
    int mid = (l + r) >> 1,res = inf;
195
    if(L <= mid)
196
        res = min(res,queryMin(rt << 1,l,mid,L,R));
197
    if(R > mid)
198
        res = min(res,queryMin(rt << 1 | 1,mid + 1,r,L,R));
199
    return res;
200
}
201
signed main()
202
{
203
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
204
    cin >> n;
205
    for(int i = 1;i <= n;i++)
206
        cin >> a[i];
207
    build(1,n,1);
208
    cin >> m;
209
    while(m--)
210
    {
211
        cin >> opt >> l >> r;
212
        if(opt == 1)
213
        {
214
            cin >> x;
215
            modifySum(1,1,n,l,r,x);
216
        }
217
        if(opt == 2)
218
        {
219
            cin >> x;
220
            modifyMax(1,1,n,l,r,x);
221
        }
222
        if(opt == 3)
223
        {
224
            cin >> x;
225
            modifyMin(1,1,n,l,r,x);
226
        }
227
        if(opt == 4)
228
            cout << querySum(1,1,n,l,r) << '\n';
229
        if(opt == 5)
230
            cout << queryMax(1,1,n,l,r) << '\n';
231
        if(opt == 6)
232
            cout << queryMin(1,1,n,l,r) << '\n';
233
    }
234
}

Seg Beats 其实不止可以给线段树用，它实际上是一种把区间最值操作转化为区间加减的 Trick，因此，面对带插入的问题，你甚至可以在平衡树上跑这个东西，~~只是代码还能再多 100 多行~~。

10.线段树合并

就是把两棵线段树所维护的信息合并起来。

显然，静态的线段树合并没有什么实际意义，最好的方法就是全部拉出来重构。

所以我们常常是合并动态开点的线段树。

过程和 FHQ Treap 差不多，如果遇到 $A$ 树中有一个结点而 $B$ 树中没有，则直接返回这个结点。

如果已经递归到叶子结点，就合并他们的信息（就是对两个叶子结点进行一次维护的操作），然后返回。

代码分在线和离线两种。

先讲离线的，就是直接将 $B$ 树的信息合并到 $A$ 树中。但是后面就不能有修改操作了，否则会导致信息错乱。

代码很简单：

1
inline int merge(int L,int R,int l,int r)
2
{
3
    if(!L || !R)
4
        return L | R;
5
    if(l == r)
6
    {
7
        tree[L].mx += tree[R].mx;
8
        tree[L].maxid = l;
9
        return L;
10
    }
11
    int mid = (l + r) >> 1;
12
    lson(L) = merge(lson(L),lson(R),l,mid);
13
    rson(L) = merge(rson(L),rson(R),mid + 1,r);
14
    pushup(L);
15
    return L;
16
}

在线的做法就是每次合并就新开一个点，把两棵线段树的信息都合并进去，缺点就是空间占用太大了。

11.线段树分裂

对于一个无序的序列，分裂显然没有什么用，所以我们一般分裂的是权值线段树。

时刻记住，线段树是 Leafy Tree，所以单独一个区间会分裂出来一条链。

但是我觉得这玩意好像考的很少，感觉还是合并会多一点。

具体操作就先分三类讨论：

现在的区间和分裂区间无交集：直接返回
现在的区间和分裂区间有交集：新建结点，往子结点走
被完全包含：断开原有的边，接到新树下方

12.线段树优化建图

虽然连边是 $\Omicron(1)$ 的无法优化了，但是有的时候，边的数量会很多，这个时候就该优化建图了。

线段树可以处理 $[l1,r1](l1 \le r1)$ 向 $[l2,r2](l2 \le r2)$ 连边的问题，这个区间可以是单点。

我们构建两个线段树，叶子结点是给你的点，第一棵从父亲向儿子连边，叫做出树，第二棵从儿子连向父亲，叫做入树。两棵树可以共用叶子结点，也可以分别建，再从出树到入树对应连边。

这些点都是多加的虚点，注意在跑图论算法的时候不要计入贡献。

分几种情况：

(1) 单点连区间

我们在入树中找到单点，再将连的区间按照线段树的套路拆成出树上的 $\Omicron(\log n)$ 个区间，然后单点连向拆分出的区间。

(2) 区间连单点

把上面的出入反一下。

(3) 区间连区间

我们新建一个虚点 $p$ ，同样的拆分区间。入树中的点连向 $p$ ， $p$ 再连向出树中的点。

可以发现，边的数量是 $\Omicron(n \log n)$ 的，时间复杂度可以优化为 $\Omicron(n \log n)$ 。

13.线段树分治

我觉得这个东西还不如叫时间分治，只是有区间操作用线段树维护会更快一点。

实际上就是一个操作，直接操作是容易的，但是难以删除，并且对时间轴上的一个区间生效，那我们就可以按照线段树的方式拆分区间，在 $\log n$ 个区间上打上标记，并在叶子结点计算答案。

实现上，我们线段树每个结点是一个 vector，存储这个结点该加入的操作。我们先添加操作，然后遍历整棵线段树，进入一个结点就加入所有操作，遍历到叶子结点的时候返回答案，离开一个结点就撤销加入的操作。

因此，我们就可以维护出现的时间，将定点删除操作转化为撤销操作。维护你需要的操作还需要其他东西，比如线性基，并查集等，并且你得考虑是否能方便的撤销。

14. 猫树 & 猫树分治

猫树

有的时候我们要维护的信息既不满足可重复贡献性，直接合并的复杂度也无法接受。这个时候就应该用猫树了。

猫树是一种静态的线段树，空间复杂度为 $\Omicron(n \log n)$ ，但是能做到每次查询仅需要 $\Omicron(1)$ 次合并。

具体来讲，假设一个结点维护的是 $[l,r]$ 的信息并，那我们额外维护 $[l,mid]$ 的后缀和与 $[mid + 1,r]$ 的前缀和。

然后，对于一个区间 $[L,R]$ 的查询，我们可以找到结点 $[L,L]$ 与结点 $[R,R]$ 的 LCA，设其为 $P$ 。显然， $[L,R] \subset P$ ，我们只需要将 $P$ 中 $[L,mid]$ 与 $[mid + 1,R]$ 的信息合并起来就行。

我们~~惊奇的~~发现，如果用堆式建树，那么 LCA 的编号就是两个叶子结点编号的 LCP，即 x >> bits[x ^ y]，其中 x,y 是两结点编号，bits[x] 表示 $\lfloor \log _ 2 x \rfloor + 1$ 。

然后对于 $L = R$ 的情况特判就行。

猫树分治

你可以把这玩意看作在序列上跑的点分治。

Eg. Luogu P6240 好吃的题目↗

题意：对序列 $a$ 的一个区间 $[l _ i,r _ i]$ 内所有物品 $(h _ i,w _ i)$ 做容量为 $t _ i$ 的 01 背包。

考虑分治，我们把询问分成两类：跨过中点的与没跨过中点的。没跨过中点的直接下传去下一层做，重点看跨过中点的。

我们发现，这和上面写的猫树的一次查询很像，于是我们考虑将一层视作一个结点，求 $[l,mid]$ 的后缀背包与 $[mid + 1,r]$ 的前缀背包，然后进行合并。

但是又有个问题，这里不支持 $\Omicron(t ^ 2)$ 的背包合并。但是我们发现，背包问题等价于 $(\max,+)$ 卷积，并且我们只需要求特定的一项的值，于是可以用卷积的定义来计算， $Ans = \max _ {p = 0} ^ {t _ i} \{ suf _ {l _ i,p} + pre _ {r _ i,t _ i - p} \}$ 。

时间复杂度是 $T(n) = 2T(\frac{n}{2}) + \Omicron(nt)$ ，主定理算出来是 $\Omicron(nt \log n)$ ，空间复杂度是 $\Omicron(nt)$ 。

可以直接用猫树做在线的，但空间会多一个 $\log$ 。

Addition.一些小 Tricks

线段树维护操作序列

就是把操作序列抽象成普通序列，然后放到线段树上维护。

只要这个操作序列可以抽象成幺半群，那就可以用线段树维护。

Eg. Luogu P4588↗

我们用线段树维护区间乘积，对于 $1$ 操作，把 $i$ 处的值修改为 $x$ ，对于 $2$ 操作，把 $x$ 处的值修改为 $1$ 。

查询都可以不写，直接求 tree[root] 处的值就好了。

二维偏序 & 树套树

因为本人不太喜欢 CDQ 分治，所以决定在这里就写二维偏序。

如果是离线的二维数点，我们可以直接扫描线 + 树状数组来解决，如果值域太大，也可以用主席树解决，离散化后对每一个横坐标新建一个版本并进行更改。查询可以直接用主席树惯用套路，用右横坐标的版本减去左横坐标的前一个版本来构建区间的树，然后在上面跑纵坐标的区间查询就行。

但是放到动态呢？你可以说加个时间维度，跑三维偏序，~~但我就喜欢用纯 DS~~。

我们可以用树套树维护这个，外层树可以是树状数组这种方便查询前缀的 DS，开不下可以换成线段树，内层一般不会让你开下第二个树状数组，于是我们可以选择权值树状数组或者平衡树。

两个做比较的话，就是里面放线段树的空间会大一点，平衡树的时间会大一点。

然后线段树同样可以作为外层树，但是就必须对整条链进行操作，不能打标记。

Thanks for reading!

数据结构Part 2

2025 1月 08 周三

6984 字 · 38 分钟

算法学习笔记 OI 数据结构