# 前置知识

初始版本是这个:神奇的线段树(上),初始版本中的攻略并不完全,没有懒标记部分,因此在本文(2.0 版本)中,将更新更详细的讲解,以及时间复杂度的证明,补充懒标记部分。

# 线段树

线段树是一种基于分治思想二叉树结构,用于在区间上进行信息统计。

# 那么线段树长什么样子呢?

  1. 线段树上的每一个节点都代表着一个区间
  2. 线段树的根节点代表着最大的统计范围;
  3. 线段树的每一个叶结点的长度都是 1,也就是唯一值;
  4. 对于每个内部节点 [L,R] ,它的左子节点都是 [L,mid] ,右子节点都是 [mid+1,R] ,其中 mid 的值为 mid=(L+R)/2 (向下取整)。

区间视角

二叉树视角

从图中可以看出来,线段树的存储就是标准二叉树的存储方法。
二叉树的一维数组存储:

  1. 根节点的编号为 1;
  2. 对于节点 x,它的父节点为 x/2;
  3. 它的左子节点为 2x;
  4. 它的右子节点为 2x+1;

# 线段树的基本操作

# 由两个子节点计算根节点(push_up)

需要根据线段树中节点的信息来计算,因此,需要根据不同的题意,具体问题具体分析。

# 由根节点计算两个子节点(push_down)

该操作比较复杂,因此放在下篇文章中来讲。

# 建立线段树(Build)

建立线段树很好理解,分为以下几个步骤:

  1. 存储当前节点的左右儿子;
  2. 如果当前节点的左右儿子相等,说明走到了一个叶子节点,结束递归即可;
  3. 计算 mid,注意这里一定要向下取整
  4. 递归 左 右子节点;
  5. 最关键的一个步骤, push_up(u); ,其中 u 是当前节点。
void build(int u, int l, int r) {
    // 存储当前左右节点到数组;
    tree[u].l = l, tree[u].r = r;
    // 找到叶子结点,结束递归;
    if (l == r) return ;
    // 计算 mid,注意向下取整;
    int mid = (l + r) / 2;
    // 递归左右节点;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    // 关键步骤 push_up
    push_up(u);
}

# 查询(Query)

假如,问题是求一段区间 [5,9] 的最大值,那么,我们线段数节点 存储的信息 就是 每个区间的最大值

假设,使用 [L,R] 表示查询的区间,用 [Tl,Tr] 表示线段树中,当前搜索的区间,那么查询区间当前搜索区间可能有下面的情况:

  1. 查询区间完全包含了当前搜索区间,说明我们已经找到了查询区间

  2. 查询区间当前搜索区间右边,也就是 Tl <= L <= Tr <= R

    此时,需要查看 mid 的位置来进行讨论

    1. 如果 L>mid ,则只需要递归右面 [mid+1, R]

    2. 如果 L<=mid ,则需要递归左右两面,因为我们在建立线段树的时候,是根据 mid 来创建分支 (子树) 的。

      这里还有一个关键点,那就是虽然会有递归两边的情况。但是因为右边 [L,mid] 在下一次递归中就已经完全在查询区间内部,变成了情况 1,所以右边只会被递归一次,不会对时间复杂度整体造成影响。

  3. 查询区间当前搜索区间左边,与情况 2完全对称的操作,因此不再赘述。

  4. 查询区间完全在当前搜索区间内部。

    此时,也需要根据 mid 的位置来进行讨论:

    1. 如果 R<=mid ,则只需要递归左边 [L, mid]

    2. 如果 L>mid ,则只需要递归右边 [mid+1, R]

    3. mid[L,R] 中间,则需要递归两边,这就需要考虑到一个问题,递归两边会不会影响整体复杂度呢?其实是不会的,我们观察这种情况下递归左右两面之后,查询区间就完全包含当前区间(递归后,左当前区间是 [L,mid] ,右当前区间是 [mid+1,R] ,它俩组成整个查询区间)

      也就是变成了情况 1,所以这种情况也只会分裂一次,因此不会影响整体复杂度。

# 修改(Modify)

修改操作与查询非常类似,可以说是查询的简单版,因此这里就不过多赘述,在应用代码中会详细注释。

# AcWing 1275. 最大数

给定一个正整数数列 a1,a2,…,an,每一个数都在 0∼p−1 之间。

可以对这列数进行两种操作:

  1. 添加操作:向序列后添加一个数,序列长度变成 n+1;
  2. 询问操作:询问这个序列中最后 L 个数中最大的数是多少。
    程序运行的最开始,整数序列为空。

一共要对整数序列进行 m 次操作。

写一个程序,读入操作的序列,并输出询问操作的答案。

输入格式

第一行有两个正整数 m,p,意义如题目描述;

接下来 m 行,每一行表示一个操作。

如果该行的内容是 Q L,则表示这个操作是询问序列中最后 L 个数的最大数是多少;

如果是 A t,则表示向序列后面加一个数,加入的数是 (t+a) mod p。其中,t 是输入的参数,a 是在这个添加操作之前最后一个询问操作的答案(如果之前没有询问操作,则 a=0)。

第一个操作一定是添加操作。对于询问操作,L>0 且不超过当前序列的长度。

输出格式

对于每一个询问操作,输出一行。该行只有一个数,即序列中最后 L 个数的最大数。

数据范围

1≤m≤2×10^5,
1≤p≤2×10^9,
0≤t < p

输入样例

10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99

输出样例

97
97
97
60
60
97

样例解释

最后的序列是 97,14,60,96。

# 题目分析

题意清晰明了。

给出一个长度为 n 的序列,每个数在 0~p-1 之间。有两个操作:

  1. 单点修改:在区间中添加一个数(添加到末尾);
  2. 查询:某个区间内的最大值(从 L 到末尾 [L, n] );

# 题目描述

本题属于比较裸的可以用线段树解决的题目,主要是用本题熟悉一下线段树的实战应用

# Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 200010;
int m, p;
struct Node {
    int l, r;
    // 节点中存储用来计算的信息。
    // 根据题意,本题需要存储 区间 [l, r] 中的最大值。
    int v;
}tree[N * 4];
// 子节点信息计算父节点信息
void pushup(int u) {
    tree[u].v = max(tree[u * 2].v, tree[u * 2 + 1].v);
}
void build(int u, int l, int r) {
    tree[u] = {l, r};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
    // 注意 这里因为本题默认最大值是 0  所以初始化时候 每个节点最大值也都是 0
    //pushup (u);   所以这里不需要 pushup
}
int query(int u, int l, int r) {
    // 查询区间 已经在 当前搜索区间 内 则返回结果
    if (tree[u].l >= l and tree[u].r <= r)  return tree[u].v;
    int mid = tree[u].l + tree[u].r >> 1;
    int res = 0;
    // 左边有交集 递归左边 递归时候查询区间不变 节点编号改变即可
    if (l <= mid) res = query(u * 2, l, r);
    // 右边有交集 递归右边 并维护最大值
    if (r > mid) res = max(res, query(u * 2 + 1, l, r));
    return res;
}
// 修改从叶子节点开始修改 最后使用 pushup 操作向上更新
//u 为当前节点编号 x 为叶子节点边界 [x, x]  v 是更新后的最大值
void modify(int u, int x, int v) {
    // 找到对应的叶子节点 则更新
    if (tree[u].l == x and tree[u].r == x) tree[u].v = v;
    else {
        // 否则更新左面 或者 右面 
        // 注意这里的左右必有一个更新 (与查询不同的地方)
        // 这样才能 递归到叶子节点
        int mid = tree[u].l + tree[u].r >> 1;
        if (x <= mid) modify(u * 2, x, v);  // 递归左面
        else modify(u * 2 + 1, x, v);  // 递归右面
        pushup(u);  // 从叶子节点 向上更新
    }
}
int main() {
    // 因为添加的数是上次查询的 所以还要存一下上次查询的结果
    int n = 0, last = 0; 
    scanf("%d%d", &m, &p);
    //// 建树 A 操作增加节点  最大操作数量是 m 所以最大节点数量也是 m 
    build(1, 1, m);
    
    char op[2];
    int x;
    while (m -- ) {
        scanf("%s%d", op, &x);
        if (*op == 'Q') {
            // 查询区间的范围 是最后 x 个数 也就是 [n-x+1, n]
            last = query(1, n - x + 1, n);
            printf("%d\n", last);
        } else {
            // 修改 既在末尾增加节点
            modify(1, n + 1, ((long long)last + x) % p);
            n ++ ;
        }
    }
    return 0;
}

# AcWing 245. 你能回答这些问题吗

给定长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:

  1. 1 x y ,查询区间 [x,y] 中的最大连续子段和,即 maxxlryi=lrA[i]max_{x≤l≤r≤y}{∑i=lrA[i]}
  2. 2 x y ,把 A [x] 改成 y。
    对于每个查询指令,输出一个整数表示答案。

输入格式

第一行两个整数 N,M。

第二行 N 个整数 A [i]。

接下来 M 行每行 3 个整数 k,x,y,k=1 表示查询(此时如果 x>y,请交换 x,y),k=2 表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

数据范围

N≤500000,M≤100000,
−1000≤A[i]≤1000

输入样例

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

输出样例

2
-1

# 题目描述

本题的题意也是比较清晰的。

给出一个长度为 N 的数列,以及两种操作:

  1. 查询操作:查询一个区间的最大连续子段和
  2. 单点修改:把区间中的一个数 A [i] 修改成 y;

那么这里,就不得不解释一下最大连续子段和这个概念啦。

从给出公式中我们可以看出,其实就是整个区间中 ‘和’最大的 连续子区间的 ‘和’是多少

# 题目分析

与上题相比,只是本题需要维护的属性变成最大的连续子段和。所以,我们如果知道如何维护这个属性,那么只要按照线段树的模板(类似上题的代码),就可以求出本题了。

# 用分治思想求最大连续子段和

如何分治呢?

假设,我们要求 [1,n]最大连续子段和,那么我们就可以把这个区间从中间一分为二,分成两部分

  1. 中间值mid=(1+n)/2
  2. 左边的子区间就是 [1, mid]
  3. 右边的子区间就是 [mid+1, n]

我们按照这种思路,一直递归下去,直到 节点只有一个元素 为止,也就是线段树中的叶子节点

因为叶子节点只有一个元素,所以我们就得到了它的最大连续子段和,也就是这个元素本身

现在,我们已经求出了最小区间的最大连续子段和,只需要向上回溯,通过已知的 子节点属性 求出 父节点属性


所以现在问题变成了知道 左、右 两个子节点的 最大连续子段和 ,如何求它俩的父节点的呢?

假设用 tmax 表示父节点的最大连续子段和,那么父节点的 tmax 只能处于下面三种情况,所以我们把这三种情况取最大值就是父节点的 tmax

  1. 父节点的 tmax 就在区间 [L,mid] 之中。这种情况下,自然父节点的 tmax 就等于左子节点的 tmax

  2. 父节点的 tmax 就在区间 [mid+1, R] 之中。这种情况下,自然父节点的 tmax 就等于右子节点的 tmax

  3. 父节点的 tmax 并不只在左右子区间,而是横跨两个区间。这种情况我们可以用左子区间(以 mid 作为最后元素)的最大后缀和 加上 右子区间(以 mid+1 作为起始元素)的最大前缀和


分析到这里,我们发现还要额外在节点内维护最大前缀和 Lmax最大后缀和 Rmax

关于这两个属性,我们仍然分情况讨论:

  1. 最大前缀和 Lmax:以左端点为起始元素的最大子段和。

    通过左 / 右子节点 求父节点的 Lmax,则会出现两种情况,我们取两种中的最大值:

    1. 父节点的 Lmax 就在区间 [L,mid] 之中,那么显然父节点的 Lmax 就等于左子区间的 Lmax

    2. 父节点的 Lmax 在区间 [L,R] 之中,则需要用整个左子区间的和 加上 右子区间的 Lmax

  2. 最大后缀和 Rmax:以右端点为结束元素的最大子段和。

    通过左 / 右子节点 求父节点的 Rmax,同样会出现两种情况,我们取两种情况的最大值:

    1. 父节点的 Rmax 就在区间 [mid+1,R] 之中,那么显然父节点的 Rmax 就等于右子区间的 Rmax

    2. 父节点的 Rmax 在区间 [L,R] 之中,则需要用左子区间的 Rmax 加上 整个右子区间


分析到这里,我们发现只要在维护一个区间和就可以了。

父节点的区间和 sum 就是 左子区间和 加上 右子区间和

# Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 500010;
int n, m;
int w[N];
struct Node {
    int l, r;
    // 节点中维护的四个属性:区间和,区间前缀和,区间后缀和,最大连续子段和
    int sum, lmax, rmax, tmax;
}tree[N * 4];
void pushup(Node &u, Node &l, Node &r) {
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, l.rmax + r.sum);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup(int u) {
    pushup(tree[u], tree[u * 2], tree[u * 2 + 1]);
}
void build(int u, int l, int r) {
    // 因为叶子节点 只有一个元素 所以四个属性都是 这个元素自己
    if (l == r) tree[u] = {l, r, w[r], w[r], w[r], w[r]};
    else {
        //build 代码模板
        tree[u] = {l, r};
        int mid = l + r >> 1;
        build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
        // 千万不要忘记 pushup 从叶子节点回溯 把整棵树 计算出来
        pushup(u); 
    }
}
//u 为当前节点 修改一个节点 x 的值 为 v
void modify(int u, int x, int v) {
    // 当前节点是 [x,x] 则把它的四个属性值改成 v
    if (tree[u].l == x and tree[u].r == x) tree[u] = {x, x, v, v, v, v};
    else {
        // 递归搜索 [x,x] 最后不要忘记 回溯时候 使用 pushup 把 x 向上更新
        int mid = tree[u].l + tree[u].r >> 1;
        if (x <= mid) modify(u * 2, x, v);
        else modify(u * 2 + 1, x, v);
        pushup(u);
    }
}
// 查询操作 模板代码
Node query(int u, int l, int r) {
    if (tree[u].l >= l and tree[u].r <= r) return tree[u];
    else {
        int mid = tree[u].l + tree[u].r >> 1;
        if (r <= mid) return query(u * 2, l, r);
        else if (l > mid) return query(u * 2 + 1, l, r);
        else {
            auto left = query(u * 2, l, r);
            auto right = query(u * 2 + 1, l, r);
            // 注意这里的思路 返回一个节点 因此 
            // 我们需要根据当前区间 [left,right] 构建一个(虚拟)节点 
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);  // 从根节点 1 开始 初始化线段树 
    while (m -- ) {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (k == 1) {
            if (x > y) swap(x, y);
            // 注意查询 和 修改 的时候 也从根节点 1 开始
            printf("%d\n", query(1, x, y).tmax);
        }
        else modify(1, x, y);
    }
    return 0;
}

# AcWing 246. 区间最大公约数

给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:

  1. C l r d,表示把 A [l],A [l+1],…,A [r] 都加上 d。
  2. Q l r,表示询问 A [l],A [l+1],…,A [r] 的最大公约数 (GCD)。
    对于每个询问,输出一个整数表示答案。

输入格式

第一行两个整数 N,M。

第二行 N 个整数 A [i]。

接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。

输出格式

对于每个询问,输出一个整数表示答案。

每个答案占一行。

数据范围

N≤500000,M≤100000,
1≤A[i]≤10^18,
|d|≤10^18

输入样例

5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4

输出样例

1
2
4

# 题目描述

给出一个长度为 N 的数列 A,给出两个操作:

  1. 给某个区间增加一个数;
  2. 询问某个区间的最大公约数

# 题目分析

本题略显麻烦,区别于前面两个题,本题的修改变成了区间修改,而非单点修改

但是,本题的修改并不是完整的修改,而是只有增加操作,这就启发我们可以使用差分来把区间修改变成两次单点修改,这个技巧我们在 [树状数组应用] 中已经有详细介绍,并且多此使用,如果还不熟悉的同学,需要先复习下。

使用 差分 可以把 区间增加 变成 单点增加,但是这样一来,线段树节点中存储的就是差分数组了,而不再是 原数组。这会不会对计算 最大公约数造成影响呢?

要回答这个问题,我们必须先掌握最大公约数的一个性质:

gcd(a1, a2, a3, ... ,a[n]) = gcd(a1, a2-a1, a3-a2, ... , a[n]-a[n-1])

要证明这个性质,我们可以使用 A>=B 和 B>=A 推出 A=B 的方法:

  1. 对于上公式中,左边 <= 右边的情况。我们知道通过更相减损术求最大公约数有公式: gcd(a, b)=gcd(a-b, b) ;所以,如果 d 是左边的最大公约数,那么 d 也一定是右边的最大公约数。

  2. 对于上公式中,左边 >= 右边的情况。假设 d 是右边的最大公约数,那么 d 一定是 a1 的约数,同时 d 也是 a2-a1 的约数,所以可以推出来 d 同样是 (a2-a1)+a1=a2 的约数。以此类推, d 能整除左边。

  3. 综上,我们可以推出上述性质。

现在,有了这个性质的加持,我们可以维护差分数组 b,求 b 的最大公约数就等价于求原数组的最大公约数

因为求差分数组的方法是 b[i]=a[i]-a[i-1] ,所以我们可以把上一个公式再次变化为: gcd(a1, b2, b3, ... , b[n])

进一步的,如果我们把这个求区间 a [1~n] 的公式扩展为求 [l,r] 的公式就变成了 gcd(a[l], b[l+1, r])

也就是说,我们只需要求出 A[l] 以及区间 b [l+1,r] 的最大公约数即可,那差分数组 b 我们是在线段树节点中动态维护的,所以直接查询即可,那么原数组中的 A [l] 要怎么求呢?其实就是使用前缀和差分数组还原成原数组。所以,我们还需要在线段树节点中维护一个前缀和的属性。

如此,使用这种方法,我们就把区间增加,转换为两次单点修改

总结一下就是,树状数组节点存储的数组是差分数组,我们要维护的信息有两个,一个前缀和 用来求原数组 a [l], 一个最大公约数 用来求 gcd (a [l], gcd (b [l+1, r]))

# Code

实现上,只要抄一下线段树模板,把在 pushup 中维护最大公约数即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
typedef long long LL;
int n, m;
struct Node {
    int l, r;
    LL sum, d;
}tree[N * 4];
LL a[N];
LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node & r) {
    u.sum = l.sum + r.sum;  // 差分的前缀和  就是区间和
    u.d = gcd(l.d, r.d);
}
void pushup(int u) {
    pushup(tree[u], tree[u * 2], tree[u * 2 + 1]);
}
// 线段树模板
void build(int u, int l, int r) {
    if (l == r) {
        LL b = a[r] - a[l - 1];  // 差分计算
        tree[u] = {l, l, b, b};  // 添加节点信息到叶子节点
    } else {
        tree[u].l = l, tree[u].r = r;  // 记录当前节点区间 忘记就会 error SF。
        int mid = l + r >> 1;
        build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int x, LL v) {
    if (tree[u].l == x and tree[u].r == x) {
        LL b = tree[u].sum + v;  // 单点增加
        tree[u] = {x, x, b, b}; // 更新节点信息
    } else {
        int mid = tree[u].l + tree[u].r >> 1;
        if (x <= mid) modify(u * 2, x, v);
        else modify(u * 2 + 1, x, v);
        pushup(u);
    }
}
Node query(int u, int l, int r) {
    if (tree[u].l >= l and tree[u].r <= r) {
        return tree[u];
    } else {
        int mid = tree[u].l + tree[u].r >> 1;
        if (r <= mid) return query(u * 2, l, r);
        else if (l > mid) return query(u * 2 + 1, l, r);
        else {
            auto left = query(u * 2, l, r);
            auto right = query(u * 2 + 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    build(1, 1, n);
    
    LL d;
    int l, r;
    char op[2];
    while (m -- ) {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q') {
            auto left = query(1, 1, l);
            Node right({0, 0, 0, 0});
            if (l + 1 <= r) right = query(1, l + 1, r);
            printf("%lld\n", abs(gcd(left.sum, right.d))); // 用公式 gcd (a [l], b [l+1, r]) 计算结果
        } else {
            scanf("%lld", &d);
            modify(1, l, d);
            // 需要特判一下 r == n 的情况
            if (r + 1 <= n) modify(1, r + 1, -d); // 注意区间增加 变成 两个单点增加
        }
    }
    return 0;
}

未完待续

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

A Cat Without Sugar 微信支付

微信支付

A Cat Without Sugar 支付宝

支付宝