Cloud_Player's Notes
0%

树状数组与线段树

发表于 更新于
本文字数： 12k 阅读时长 ≈ 11 分钟

b站视频链接：北京理工大学ACM冬季培训课程
课程刷题地址 2020BIT冬训-树状数组&线段树 但是没得密码。。。
本篇博文为看视频学习时的记录与自己的一些总结
学习笔记合集：算法入门基础

  • 树状数组与线段树
    • 树状数组
      • 由前缀和引入
        • 导引问题
      • 引入树状数组
        • $\text{lowbit}(x)$ 的求法
        • 构造树状数组 $C_i$
        • 区间查询操作
        • 单点更新操作
        • 二维树状数组模板
      • 树状数组应用
        • 求逆序对
        • 对上面问题的引申——离散化
        • 区间更新，单点查询
        • 区间修改，区间查询
      • 树状数组的优缺点
    • 线段树
      • 导引问题
      • 引入线段树
        • 线段树的属性
        • 线段树的定义
        • 线段树的构造
        • 单点更新
        • 区间查询
      • 线段树的区间更新
        • lazy 标记与延迟更新
        • 区间更新
        • 区间更新的区间查询
        • 更好的代码
      • 线段树的应用
        • 线段树 + 区间合并
      • 线段树的优缺点

树状数组与线段树

树状数组

由前缀和引入

$A$ 为 $N$ 个数所在的数组，$B$ 为另一个新的数组
令 $B$ 数组的第 $i$ 项为 $A$ 数组的 $A_0$ 至 $A_i$ 项之和

即：

$$
B_i = A_0 + A_1 + A_2 + \dots + A_i
$$

则有：

$$
B_i = B_{i-1} + A_i \ \ \ \ (B_0 = A_0)
$$

有时为了方便，$A$、$B$ 数组下标从 $1$ 开始

前缀和的应用：

区间求和，求 $A$ 数组的 $100$ 至 $200$ 项之和

$$
A_{100} + \dots + A_{200} = B_{200} - B_{99} \ \ \ \ O(n) \Rightarrow O(1)
$$

当区间求和量比较大的时候，通过预处理前缀和数组，极大地减少了计算量

导引问题

有 $N$ ($N \le 50000$) 个工兵营地，已知每个营地的人数，查询一段连续的工兵营地总人数，询问的次数 $Q \le 50000$

预处理前缀和数组

有 $N$ ($N \le 50000$) 个工兵营地，已知每个营地的人数，但是每个工兵营地的人数都有可能多次发生变动，每次可能增加或减少若干人手，需要查询一段连续的工兵营地总人数，询问的次数 $Q \le 50000$

难以维护前缀和数组，还不如暴力开数组

引入树状数组

提出问题
给长度为 $n$ 的数组 $A_1, A_2, \dots, A_n$，多次修改操作和查询操作，修改操作修改数组某一个元素的值，查询操作查询 $A_1 + A_2 + \dots + A_x$ 的值

朴素做法

  • 每次 $O(1)$ 修改数组的值，$O(n)$ 求和
  • 求出前缀和数组 $sum_i = a_1 + a_2 + \dots + a_i$，每次 $O(1)$ 查询，$O(n)$ 修改

为了引入树状数组，先构造二叉树，叶子结点代表 $A_1$ ~ $A_8$
对二叉树变形，定义每一列的顶端元素为树状数组元素，其中 $C_i$ 代表子树的叶子结点的权值之和，例如 $C_6 = A_6 + A_5$

两个规律：

  • $i$ 为奇，$C_i = A_i$
  • $C_i$ 一定包含 $A_i$，且 $A_i$ 是其包含的最后一个

引入树状数组 $C_1, C_2, \dots, C_n$，其中

$$C_i = A_i + A_{i-1} + \dots + A_{i-\text{lowbit}(i)+1}$$

$\text{lowbit}(i)$：将 $i$ 转换为二进制，最低位的 $1$ 所代表的值
$\text{lowbit}(i)$ 决定 $C_i$ 包含多少项

$5 = (101)_2 \ \ \ \ \ \ \text{lowbit}(5) = (1)_2 = 1$
$6 = (110)_2 \ \ \ \ \ \ \text{lowbit}(6) = (10)_2 = 2$
$8 = (1000)_2 \ \ \ \ \text{lowbit}(8) = (1000)_2 = 8$

$\text{lowbit}(1)=1\ \ \ \ C_1 = A_1$
$\text{lowbit}(2)=2\ \ \ \ C_2 = A_2 + A_1$
$\text{lowbit}(3)=1\ \ \ \ C_3 = A_3$
$\text{lowbit}(4)=4\ \ \ \ C_4 = A_4 + A_3 + A_2 + A_1$
$\text{lowbit}(5)=1\ \ \ \ C_5 = A_5$
$\text{lowbit}(6)=2\ \ \ \ C_6 = A_6 + A_5$
$\text{lowbit}(7)=1\ \ \ \ C_7 = A_7$
$\text{lowbit}(1)=8\ \ \ \ C_8 = A_8 + A_7 + A_6 + A_5 + A_4 + A_3 + A_2 + A_1$

$\text{lowbit}(x)$ 的求法

法 1：
若 $x$ 为奇，其二进制的最后一位必为 $1$，则 $x-1$ 的最后一位必为 $0$
则 $x \And (x-1) = x-1$，$x - (x \And (x - 1)) = 1$
奇数的 $\text{lowbit}$ 一定是 $1$
若 $x$ 为偶，$x \And (x-1)$ 使得从最低位的 $1$ 开始全置为 $0$
$x - (x \And (x - 1))$ 减出来的结果就是 $\text{lowbit}(x)$

1
2
3
4
int lowbit(x)
{
    return x - (x & (x - 1));    
}

法 2：
利用补码的性质
负数的二进制补码等于对应正数的反码加一
可以得到 $\text{lowbit(x) = x & (-x)}$

1
2
3
4
inline int lowbit(int x)
{
    return x & (-x);
}

构造树状数组 $C_i$

已知原始的 $A_i$ 数组（初始状态）
现在又有了 $\text{lowbit}(x)$ 函数
如何构造出树状数组 $C_i$ ？
其实树状数组的构造就是更新操作！

区间查询操作

先实现前缀和，利用 $C_i$ 求出 $A$ 数组中的前 $i$ 项的和
比如 $i = 7$ 时，前七项和为：$a_1 + a_2 + \dots + a_7$

$$\begin{array}{lcl} a_1 + a_2 + \dots + a_7 & = & (a_7) + (a_6 + a_5) + (a_4 + a_3 + a_2 + a_1)\\ & = & c_7 + c_6 + c_4 \\ & = & c_{(111)_2} + c_{(110)_2} + c_{(100)_2} \end{array}$$

规律：
$\text{lowbit}(i)$ 决定 $C_i$ 包含多少项
每加上一个 $C_i$ 就让 $i = i - \text{lowbit}(i)$

求和实现代码 $O(\log n)$

1
2
3
4
5
6
7
int sum(int i)
{
    int ret = 0;
    while(i)
        ret += C[i], x -= lowbit(i);
    return ret;
}

区间查询：$sum( R ) - sum( L - 1 )$

单点更新操作

$i$ 结点的父亲结点是 $i + \text{lowbit}(i)$ 结点
每次修改会影响这个结点到根结点的路径上的点

更新代码 $O(\log n)$

1
2
3
4
5
void update(int i, int val)             // 单点更新（影响多个 C 数组元素）
{
    while(i <= n)
        c[i] += val, i += lowbit(i);    // 由叶子结点向上更新 C 数组
} // 更新（从小到大）是查询（从大到小）的逆过程

二维树状数组模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void update(int x, int y, int z)
{
    int i = x;
    while (i <= n) {
        int j = y;
        while (j <= m) {
            c[i][j] += z;
            j += lowbit(j); 
        }
        i += lowbit(i);
    }
}

int sum(int x, int y)
{
    int res = 0, i = x;
    while (i > 0) {
        int j = y;
        while (j > 0) {
            res += c[i][j];
            j -= lowbit(j);
        }
        i -= lowbit(i);
    }
    return res;
}

树状数组应用

求逆序对

给定 $n$ ($n \le 100000$) 个正整数，希望对其从小到大排序，如果采用冒泡排序算法，请计算需要进行的交换次数

冒泡排序的基本思想是比较相邻的元素，逆序则交换，那么交换次数的本质就是逆序对的总数，问题就转换成了如何求逆序对的总数

基本思想：开一个数组 $a[n+1]$，初始化为 $0$，$a$ 数组下标代表对应的正整数，每计一个数 $i$，就令 $a[i] = 1$，通过计算 $a[i+1]$ ~ $a[n]$ 中有多少个 $1$ 来求出 $i$ 的逆序数，这里需要多次区间求和，于是开一个树状数组 $c[n+1]$，初始化为 $0$，当计一个数 $i$ 时，就向上更新 $c$ 数组，当求 $i$ 的逆序数时，只需计算 $\text{sum}(n)-\text{sum}(i)$ 即可

对上面问题的引申——离散化

给定 $n$ ($n \le 100000$) 个正整数 $A_i$ 组成的数列 ($A_i \le 10^9$，$1 \le i \le n$)，希望对其从小到大排序，如果采用冒泡排序算法，请计算需要进行的交换次数

之前的算法使用数组下标代表对应的正整数，这里正整数最大达到 $10^9$，不可能开这么大的数组，需要进行 离散化

离散化是一种常用的技巧，有时 数据范围太大，自身无法作为数组的下标保存对应的属性，当数据只与它们之间的相对大小有关，而 与具体值无关 时，则可以进行离散化，总之，离散化是在 不改变数据相对大小 的条件下，对数据进行相应的缩小

方法：把对应的数据和 $1$ 至 $N$ 建立一一映射的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 建立结构体
struct Node
{
    int val;        // 原始数值
    int order;      // 原始下标
}a[100001];
int b[100001];

// 对数组 a 按 val 从小到大排序；
// 此时，val 和结构体的新下标就是一个一一映射关系
// 并且满足原来的相对大小关系

// 更新 b 数组（离散化数组）
for (i = 1; i <= N; i++)
    b[a[i].order] = i;

离散化示例

重复元素处理

1
2
3
4
5
6
sort(a+1, a+1+N, cmp);
b[a[1].order] = 1;
for (i = 2, count = 1; i <= N; i++){
    if (a[i].val == a[i - 1].val)   b[a[i].order] = count;
    else b[a[i].order] = ++count;
}

区间更新，单点查询

有 $N$ ($N \le 100000$) 个气球排成一排，从左到右依次编号为 $1$，$2$，$3$，$\dots$，$N$，每次给定两个整数 $a$ 和 $b$ ($a \le b$)，表示从气球 $a$ 到气球 $b$ 依次给每个气球涂一次颜色，$N$ 次涂色后，计算每个气球被涂过几次颜色

变化：更新的是区间，查询的是单点

需要一个“区间更新，单点查询”的树状数组
通过 差分 的方法，数组中记录每个元素与前一个元素的差，这样把问题转化为常规树状数组！

单点查询
若原数组为 $a[i]$，设数组 $d[i] = a[i] - a[i-1]$ ($a[0] = 0$)，则可以通过求 $d[i]$ 的前缀和实现单点查询 $a[i]$
区间修改
当给区间 $[l,r]$ 加上 $x$ 的时候，只需给 $d[l]$ 加上 $x$，给 $d[r+1]$ 减去 $x$ 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 单点更新差分，为区间修改做准备（c 为树状数组）
void add(int p, int x){
    while (p <= n) c[p] += x, p += p & -p;
}
// 区间修改（通过两个端点的更新，实现区间修改的目的）
void range_add(int l, int r, int x){
    add(l, x), add(r + 1, -x);
}
// 单点查询（因为差分，所以单点值即前缀和）
int ask(int p){
    int res = 0;
    while (p) res += c[p], p -= p & -p;
    return res; 
}

区间修改，区间查询

金箍棒由 $N$ 段相同长度的金属棒连接而成，初始每段金属棒的值都是 $1$，并且从 $1$ 至 $N$ 编号，可以增加金箍棒任意连续的一段的所有金属棒的值，可以查询（$Q$ 次）执行 $M$ 次操作后某一段金箍棒的总值

变化：区间修改，区间查询

位置 $p$ 的前缀和：

$$\begin{array}{lcl} \sum\limits_{i=1}^{p}a[i] & = & \sum\limits_{i=1}^{p}\sum\limits_{j=1}^{i}d[j] \\ & = & \sum\limits_{i=1}^{p}d[i] * (p - i + 1) \\ & = & (p + 1)\sum\limits_{i=1}^{p}d[i] - \sum\limits_{i=1}^{p}d[i] * i \end{array}$$

维护两个数组的前缀和（树状数组）即可，$c1[i] = d[i]$，$c2[i] = d[i] * i$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 维护两个树状数组
void add(int p, int x){
    for (int i = p; i <= n; i += i & -i)
        c1[i] += x, c2[i] += x * p;
}
// 区间修改
void range_add(int l, int r, int x){
    add(l, x), add(r + 1, -x);
}
// 前缀和查询，即查询区间 [1, p] 的和
int ask(int p){
    int res = 0;
    for (int i = p; i; i -= i & -i)
        res += (p + 1) * c1[i] - c2[i];
    return res; 
}
// 区间查询
int range_ask(int l, int r){
    return ask(r) - ask(l - 1);
}

树状数组的优缺点

优点：代码短小，实现简单；

缺点：只能求和，不能求最大/小值

线段树

导引问题

金箍棒升级了！
金箍棒由 $N$ 段相同长度的金属棒连接而成，初始每段金属棒的值都是 $1$，并且从 $1$ 至 $N$ 编号，可以改变金箍棒任意连续的一段的所有金属棒的值，可以查询（$Q$ 次）执行 $M$ 次操作后某一段金箍棒的总值

区间更新，但不是增加或减少，而是直接修改
树状数组不能解决这个问题

新的数据结构：线段树

引入线段树

假设有编号从 $1$ 到 $n$ 的 $n$ 个点，每个点都存了一些信息，用 $[L, R]$ 表示下标从 $L$ 到 $R$ 的区间信息

线段树原理：
将 $[1, n]$ 分解成若干特定的子区间（数量不超过 $4 * n$），然后，将每个区间 $[L, R]$ 都分解为少量特定的子区间，通过对这些少量子区间的修改或者统计，来实现快速对 $[L, R]$ 的修改或者统计

线段树（Segment Tree）又称为区间树（Internal Tree），是一颗平衡二叉树，非完全二叉树，树上的每一个节点代表一段区间

线段树划分区间采用的是二分的思想，比树状数组更加直白

线段树的属性

  • 每个区间的长度是区间内整数的个数
  • 叶子结点长度为 $1$，不能再分
  • 若一个结点对应的区间是 $[a, b]$，则其子区间对应的节点分别是 $[a, \dfrac{(a+b)}{2}]$ 和 $[\dfrac{(a+b)}{2} + 1, b]$
  • 线段树的高度是：$\left\lceil \log_{2} (b-a+1) \right\rceil + 1$
  • 线段树把区间上的任意一条线段都分成不超过 $2 \log N$ 条（每层不超过两个）

线段树的定义

定义 SegmentNode 结构体与线段树 SegTree 数组

1
2
3
4
5
6
7
8
9
10
11
#define LL long long
struct SegmentNode
{
    LL val;             // 结点值，例如区间最大值 
    LL lazy;            // 懒惰标记，又称延迟更新标记
                        // 可以根据题目增加更多的元素
};
int A[maxn];            // 原始数组
SegmentNode SegTree[maxn<<2];       // 定义线段树，开原始数组的 4 倍大
// SegmentNode SegTree[4*maxn];
// 数组存二叉树，用完全二叉树的编号作为数组下标

线段树的构造

PushUp 函数更新结点信息
build 函数构造根为 $rt$，$A$ 区间为 $[l, r]$ 的线段树
在 build 函数中调用 PushUp 函数，用于在函数回溯时向上更新线段树的结点信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// PushUp 函数更新结点信息，这里以求和为例
void PushUp(int rt)
{ 
    SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val;
    // SegTree[rt].val = SegTree[2*rt].val + SegTree[2*rt + 1].val; 
}
// 建树
// 构造根为 rt，A 区间为 [l, r] 的线段树
void build(int rt, int l, int r)
{
    if (l == r)                     // 叶子结点
    {
        SegTree[rt].val = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(2*rt, l, mid);            // 递归构造左子树
    build(2*rt + 1, mid + 1, r);    // 递归构造右子树
    PushUp(rt);                     // 回溯，向上更新
}

单点更新

假设 $A[L] += k$，区间信息为区间的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// tl，tr 表示当前结点区间，rt 表示当前线段树的根结点编号
// k 为变化值，L 为更新点的下标
void Update(int tr, int tl, int tr, int L, int k)
{
    if (tl == tr)                               // 叶结点，直接修改
    {
        SegTree[tr].val += k;
        return;
    }
    int mid = (tl + tr) >> 1;
    if (L <= mid) Update(2*rt, tl, mid, L, k);
    else Update(2*tr+1, mid+1, tr, L, k);
    PushUp(rt);                                 // 回溯，向上更新
}

区间查询

假设询问 $A[L, R]$ 的和

1
2
3
4
5
6
7
8
9
10
11
12
// [tl, tr] 表示当前区间，[l, r] 表示操作区间
// rt 表示当前结点编号
LL ask(int rt, int tl, int tr, int l, int r)
{
    if (tl == l && tr == r) return SegTree[tr].val;
    int mid = (tl + tr) >> 1;
    if (r <= mid) return ask(2*rt, tl, mid, l, r); else
    if (l > mid) return ask(2*rt + 1, mid + 1, tr, l, r); else
    {
        return ask(2*x, tl, mid, l, mid) + ask(2*x + 1, mid + 1, tr, mid + 1, r);
    }
}

另一种写法：在函数递归时保持 $[l, r]$ 操作区间不变
采用这种写法为模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// [tl, tr] 表示当前区间，[l, r] 表示操作区间
// rt 表示当前结点编号
LL Query(int rt, int tl, int tr, int l, int r)
{
    if (l <= tl && tr <= r)                 // 完全包含
        return SegTree[rt].val;
    if (l > tr || r < tl)                   // 完全不包含
        return 0;
    int mid = (tl + tr) >> 1;

    int ANS = 0;
    if (l <= mid) ANS += Query(rt<<1, tl, mid, l, r);
    // 左子区间与 [l, r] 有重叠，递归
    if (r > mid) ANS += Query(rt<<1|1, mid+1, tr, l, r);
    // 右子区间与 [l, r] 有重叠，递归
    return ANS;
    // return Query(rt<<1, tl, mid, l, r) + Query(rt<<1|1, mid+1, tr, l, r);
    // 这一句与上面四句结果等价，写的时候只写这一句就好了
}

线段树的区间更新

区间更新：
是指更新某个区间内的所有叶子结点的值，因为叶子结点会影响其相应的非叶父结点，那么回溯需要更新的非叶子结点也会有很多，如果一次性更新完，操作的时间复杂度可达 $O(n)$，$N$ 次更新操作时间复杂度就到了 $O(n^2)$

为此，引入了线段树中的延迟标记概念（lazy 标记）

lazy 标记与延迟更新

lazy 标记记录线段树当前结点是否进行了某种将要影响到其子结点的修改，记录后就可以偷懒不向下更新（不将影响传播至子结点），当查询到该结点的时候或者修改到该结点的子结点的时候再向下更新

多次更新，一次下推 / 无需要，不下推

加入 lazy 标记的线段树的 build 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 构造根为 rt，A 区间为 [l, r] 线段树
// 有 lazy 标记
void build(int rt, int l, int r)
{
    SegTree[rt].lazy = 0;           // 初始化延时标记为 0
    if (l == r)                     // 叶子结点
    {
        SegTree[rt].val = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(2*rt, l, mid);            // 递归构造左子树
    build(2*rt + 1, mid + 1, r);    // 递归构造右子树
    PushUp(rt);                     // 回溯，向上更新
}

区间更新

假设 $A[L, R] += k$

区间更新 change 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// [tl, tr] 表示当前区间，[l, r] 表示操作区间
// rt 表示当前结点编号，k 代表区间进行的更新
void change(int rt, int tl, int tr, int l, int r, int k)
{
    if (tl == l && tr == r)
    {
        SegTree[rt].lazy += k;
        return;
    }
    if (SegTree[rt].lazy) PushDown(rt, tl, tr);
    int mid = (tl + tr) >> 1;
    if (r <= mid) change(2*rt, tl, mid, l, r, k); else
    if (l > mid) change(2*rt + 1, mid + 1, tr, l, r, k); else
    {
        change(2*rt, tl, mid, l, mid, k);
        change(2*rt + 1, mid + 1, tr, mid + 1, r, k);
    }
    SegTree[rt].val = SegTree[2*rt].val + (mid - tl + 1)*SegTree[2*rt].lazy + SegTree[2*rt + 1].val + (tr - mid)*SegTree[2*rt + 1].lazy;
}

下推更新 PushDown 函数

1
2
3
4
5
6
7
8
9
10
void PushDown(int rt, int tl, int tr)
{
    SegTree[rt].val = SegTree[rt].val + (tr - tl + 1)*SegTree[rt].lazy;
    if (tl != tr)
    {
        SegTree[2*rt].lazy += SegTree[rt].lazy;
        SegTree[2*rt + 1].lazy += SegTree[rt].lazy;
    }
    SegTree[rt].lazy = 0; 
}

区间更新的区间查询

假设询问 $A[L, R]$ 的和

区间查询 ask 函数

1
2
3
4
5
6
7
8
9
10
11
LL ask(int rt, int tl, int tr, int l, int r)
{
    if (SegTree[rt].lazy) update(x, tl, tr);
    if (tl == l && tr == r) return SegTree[x].sum;
    int mid = (tl + tr) >> 1;
    if (r <= mid) return ask(2*rt, tl, mid, l, r); else
    if (l > mid) return ask(2*rt + 1, mid + 1, tr, l, r); else
    {
        return ask(2*rt, tl, mid, l, mid) + ask(2*rt + 1, mid + 1, tr, mid + 1, r);
    }
}

更好的代码

上面的区间更新的代码更符合直觉，但下面的代码更加流畅简洁
采用下面的代码作为模板
注意到，同样是完成区间更新功能的函数
上面的 change 函数在进第一个 if（return 前）时不更新当前结点的 val，而下面的 Update 函数是要更新的
并且 change 函数在递归过程中可能改变操作区间，而 Update函数在递归时保持 $[l, r]$ 操作区间不变
还要注意到两个函数 if 分类讨论情况的不同

区间更新 Update 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// [tl, tr] 表示当前区间，[l, r] 表示操作区间
// rt 表示当前结点编号，k 代表区间进行的更新
void Update(int l, int r, int k, int tl, int tr, int rt)
{
    if (l <= tl && tr <= r){
        SegTree[rt].val += k*(tr-tl+1);                 // 更新数字和，向上保持正确
        SegTree[rt].lazy += k;                          // 累加还是赋值，看需求
        return;
    }
    int mid = (tl+tr)>>1;
    PushDown(rt, mid-tl+1, tr-mid);                     // 下推以后，才准确更新子结点
                                                        // 一定要搞清楚这里为什么下推，不下推有什么后果
    if (l <= mid) Update(l, r, k, tl, mid, rt<<1);
    if (r > mid) Update(l, r, k, mid+1, tr, rt<<1|1);
    PushUp(rt);                                         // 更新本结点信息
}

下推更新 PushDown 函数

1
2
3
4
5
6
7
8
9
10
11
12
// ln，rn 分别为左子树和右子树的区间大小
void PushDown(int rt, int ln, int rn)
{
    if(SegTree[rt].lazy){                               // 下推标记
        SegTree[rt<<1].lazy += SegTree[rt].lazy;
        SegTree[rt<<1|1].lazy += SegTree[rt].lazy;
        SegTree[rt<<1].val += SegTree[rt].lazy*ln;
        SegTree[rt<<1|1].val += SegTree[rt].lazy*rn;

        SegTree[rt].lazy = 0;                           // 清除本结点标记
    }
}

区间查询 Query 函数

1
2
3
4
5
6
7
8
9
10
11
12
// [tl, tr] 表示当前区间，[l, r] 表示操作区间
// rt 表示当前结点编号
LL Query(int l, int r, int tl, int tr, int rt)
{
    if (l <= tl && tr <= r)
        return SegTree[rt].val;
    if (l > tr || r < tl)
        return 0;
    int mid = (tl+tr)>>1;
    PushDown(rt, mid-tl+1, tr-mid);                     // 下推后才准确查询子结点
    return Query(l, r, tl, mid, rt<<1) + Query(l, r, mid+1, tr, rt<<1|1);
}

注意，可以根据自己的习惯定义结构体，加入一些参数使得计算更方便

线段树的应用

要用线段树统计，必须符合区间“加法”
否则不可以通过二分子区间来得到 $[L, R]$ 的统计结果
常见的例子有：
区间数字之和 = 左区间数字之和 + 右区间数字之和
区间最大值 = $\max$ ( 左区间最大值，右区间最大值 )
区间最大公因树(GCD) = $\gcd$( 左区间 GCD，右区间 GCD )

一个问题只要能转化成对一些连续点的修改与统计问题，基本可以使用线段树来解决

线段树 + 区间合并

给定 $n$ 个整数和 $m$ 个操作，输出查询结果，操作有两类：
U A B：将第 $A$ 个元素替换为 $B$（索引从 $0$ 开始计数）
Q A B：输出 $[a, b]$ 中最长的连续递增子序列（LCIS）的长度

$[a, b]$ 中最长的连续递增子序列 $\neq$ $\text{MAX}$ ( 左区间 $max$，右区间 $max$ )
有可能跨越左右两个区间，涉及区间合并的思想

对任意一个结点：
$max$ 为当前结点综合整个区间得到的 LCIS 长度
$lmax$ 为从当前结点最左端开始的 LCIS 长度；$rmax$ 为从当前结点最右端结束的 LCIS 长度

分类讨论：

  • 左区间最右边的值 $\ge$ 右区间最左边的值
    $max$ = $\text{MAX}$ ( 左区间 $max$，右区间 $max$)
  • 左区间最右边的值 $<$ 右区间最左边的值，即 $a[mid] < a[mid + 1]$
    $lmax$ =（左区间 $lmax$ == 左区间长度 $llen$）? 左区间长度 $llen$ + 右区间 $lmax$ : 左区间 $lmax$
    $rmax$ =（右区间 $rmax$ == 右区间长度 $rlen$）? 右区间长度 $rlen$ + 左区间 $rmax$ : 右区间 $rmax$
    $max = \text{MAX}$ ( 左区间的 $max$，右区间的 $max$，左区间 $rmax$ + 右区间 $lmax$ )

线段树的优缺点

优点：应用范围广，经常用于辅助实现其他算法的优化，并且可以完全代替树状数组

缺点：代码实现稍显麻烦