本文转载自xyw813:线段树专题

前言 ඞ

本文章主要由浅入深的介绍线段树的各种操作，由于线段树特别重要。支持几乎所有的区间操作，所以笔者也会分享一些理解，同时存在难以避免的错误，还请读者指出！

线段树的定义

线段树的定义：使用树形结构通过维护操作子节点的信息，来统计区间信息的树形结构。

为什么需要线段树

支持在时间复杂度 内完成单点（区间）修改、单点（区间）查询、区间翻转、区间最值、区间众数、区间数点等一系列区间操作，具有可拓展、灵活操作等特点。

注 : 线段树支持的操作过多，本文不会提及所有操作！

如何实现基本的线段树

建树

建树非常简单！就是划分线段

image.png

我们将划分区间的操作称之为裂开区间

将其画成树形结构更加的形象

image.png

  1. 首先通过上图我们可以发现，其实线段树是一种堆式存储的形式 ， 我们设父节点的编号是 的话 ， 那么我们的左孩子是 , 右孩子是 (位运算不懂的，请查bing)。
  2. 其次通过上图我们发现区间只有一个数的结点，那就是叶子结点，这些叶子结点只存储值，当然我们也可以看成它是存储的区间信息(个人觉得这样更好理解)。
    我们知道了存储方式，以及每个结点存储的数据，那么我们就可以建树了
  3. 递归建树
void build(int u , int l , int r){

 tr[u] = {l , r , 0 , 0 };
 if (l == r) return ;

 int mid = (l + r) >> 1;           // 区间裂开

 build(ls , l , mid);
 build(rs , mid + 1 , r);
}

区间修改、查询

这里给出两种区间修改的方式 ， 请按照情况选择。

  1. 差分 ， 将区间操作转化为单点操作。
  2. 懒标记 , 优化未进行的操作。

差分

先介绍第一种方法，差分 ， 我们可以对原序列进行差分。

  • 修改操作步骤

    • 对原序列进行差分
    • 对于区间修改只需要对 点加上 C ，再对 点减去C即可（ 注意边界）

  • 查询

    • 单点查询 直接求 的前缀和 , 这个操作的是时间复杂度是
    • 区间查询 那么就需要一点技巧这里给出步骤，并附上证明
      • 步骤
        1. 考虑维护两棵线段树 ，一棵线段树维护序列差分区间和 , 另外一棵线段树维护
        2. 求区间和只需要对使用公式 $(r + 1)\sum_{i = 1}^{r} d_i - l\sum_{i = 1}^{l-1} d_i - (\sum_{i=1}^r d_i \ i - \sum_{i=1}^{l-1} d_i\ i)$
      • 证明
        1. 区间和我们可以表示成这样 (笔者是类比树状数组求区间和的方法，可能存在错误)
          $$
          \sum_{i=l}^r\sum_{j = 1}^i d_j = ( (r + 1)\sum_{i = 1}^{r} d_i - (l - 1 + 1)\sum_{i = 1}^{l-1} d_i ) - (\sum_{i=1}^rd_i \ i - \sum_{i=1}^{l-1} d_i\ i)
          $$
          核心思想：求前缀和再做差

第一种方法代码不给出，主要就是介绍思想 , 代码可以自行网络查找。如果遇到这种情况，可以借助另外一种数据结构更为方便。

懒标记

  • 区间修改、查询

先瞅瞅懒标记tag

image.png

先好好说说

  • 懒标记
    • 是什么？
      用于记录历史修改操作的区间标记，大白话就是把之前没有进行的操作进行一下。
    • 有什么用？
      用于记录历史标记，对区间进行修改时减少许多不必要的操作。
      例如：我一直对区间 操作 ， 但是我只询问 , 明显 那个区间不需要修改
    • 什么时候使用它？
      在需要对这个区间操作的时候，如果存在懒标记，那么将子节点的信息算好，懒标记再下传即可。
    • 核心要点：
      • 懒标记是给子节点用的！
      • 下传懒标记操作，实际是先通过操作父结点懒标记时算好子结点的信息，再将父结点懒标记传给子结点（这里称维护结点信息）。
      • 这个操作往往发生在查询和修改的时候（一般会另外写一个pushdown函数）

上文指到的是加法标记，其实线段树可以维护非常多的标记。本人目前还最多接触过同时维护两种运算标记。
凡是父节点信息可以通过子结点拼凑的，都是使用线段树维护。
这是一点对线段树的理解！

理解了懒标记，就好做区间修改和区间查询了。

  • 区间修改

其实看到图就是怎么修改了。
image.png

image.png

  1. 先给定一个区间 [1 , 4] , 操作方式就是懒标记停在[1 , 3] , 因为我们不要用到这个区间。 [4 , 4] 这个区间操作我们其实也可以理解成停在 [4 , 4].
  2. 注意在第二次操作的时候 , 我们对 [2 , 5] 进行操作。这时候，我们需要操作这个区间的元素 [1 , 3] , 那么在操作这个区间时 ，也就是 触 的时候 ，我们就要将懒标记下传，维护信息，然后再对对应区间进行操作（因为笔者不会如何制作动图，不然就非常的直观 , 水平菜了）。
  • 区间查询

其实区间查询就是区间修改的阉割版，不是吗？我只需要一路将需要处理的懒标记处理了，然后发挥对应区间的信息即可。

给定一张图，来看看如何进行区间查询。

image.png

我们发现，我们将 [4 , 5] 标记维护完了，父节点和子节点的信息。
怎么维护的呢？
一般步骤：

  1. 通过父节点懒标记维护子节点信息
  2. 将父节点的懒标记下传给子节点
  3. 将父节点的懒标记清除
  4. 请记住一点，父节点的信息一定是维护正确的，懒标记是用来给子节点用的。父节点拥有的懒标记，一定给父节点用，这一点非常重要！

注: 懒标记本质就是未操作完的动作，被保存了下来

  • 参考代码
#include <iostream>
#include <cstring>
#include <algorithm>

#define LL long long
#define ls u << 1
#define rs u << 1 | 1

const int N = 100010;

int n, m;
LL a[N];
struct Node {
    int l, r;
    LL sum, tag;
} tr[4 * N];

void pushup(Node &u, const Node &L, const Node &R) {
    u.sum = L.sum + R.sum;
}

void puhsdown(int u) {
    if (tr[u].tag) {
        tr[ls].sum += (tr[ls].r - tr[ls].l + 1) * tr[u].tag;
        tr[rs].sum += (tr[rs].r - tr[rs].l + 1) * tr[u].tag;
        tr[ls].tag += tr[u].tag;
        tr[rs].tag += tr[u].tag;
        tr[u].tag = 0;
    }
}

void modify(int u, int l, int r, LL c) {
    if (l <= tr[u].l && tr[u].r <= r) {      // 修改区间信息
        tr[u].sum += (tr[u].r - tr[u].l + 1) * c;   // 维护结点信息
        tr[u].tag += c;          // 打上结点标记
        return;
    }
    puhsdown(u);
    int mid = (tr[u].r + tr[u].l) >> 1;
    if (r <= mid) modify(ls, l, r, c);
    else if (l > mid) modify(rs, l, r, c);
    else {              // 区间左右孩子都有 , 裂开
        modify(ls, l, mid, c);
        modify(rs, mid + 1, r, c);
    }
    pushup(tr[u], tr[ls], tr[rs]);
}


LL query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    puhsdown(u);               // 懒标记下传
    int mid = (tr[u].l + tr[u].r) >> 1;
    LL sum = 0;

    if (r <= mid) sum = query(ls, l, r);
    else if (l > mid) sum = query(rs, l, r);
    else {
        sum += query(ls, l, mid);
        sum += query(rs, mid + 1, r);
    }
    pushup(tr[u], tr[ls], tr[rs]);
    return sum;
}

学完可以去刷【模板】线段树 1这道题。

线段树的应用

区间最值

这个维护就比较的简单 ， 因为区间最值是通过子节点拼凑出来的信息，也就是说，[3 , 5] 的最大值是 [3 , 4 , 5] 三个结点的信息拼凑出来的，这样只需要向上 pushup 即可。

image.png

就像这样 ， 通过子节点不断向上维护即可。

学完可以去刷这道题扶苏的问题 , 这题有点毒瘤。

区间最大子段和

区间最大子段和 ，可以参照这道题小白逛公园。
即，快速求出给定区间 [l , r] 的最大子段和。

对于这题也是一个区间信息拼凑的问题。

image.png

求出最大子段和的方法 :

  • 为什么是这样的呢？我们来分类讨论可能的情况
    1. 左边最大子段和是整个区间的最大子段和
      image.png
    2. 右边最大子段和是整个区间的最大子段和
      image.png
    3. 左边区间和右边区间拼接起来，组成区间最大子段和
      image.png

因为我们需要考虑三种情况，所以我们的维护方式这样的。且除此之外，没有其他的情况了。

但是问题来了 ， 如何维护区间最大左子段和、区间最大右子段和？

  • 对于区间最大左子段和我们可以通过分类讨论，来确定
    1. 直接将左孩子的最大左子段和上传
      image.png
    2. 将左孩子的整个区间和sum 和 右孩子的最大左子段和拼凑上来
      image.png

对这两种情况，我们肯定要贪心的取
求出区间最大左子段和方法:

维护区间最大右子段和方法，就是类似的啦。
直接给出方法:

如何维护区间和 ，那就非常简单啦。前面已经讲过了。(如果是新手，还请扎扎实实地学，一步一步来)

  • 参考代码
#include <iostream>
#include <algorithm>

#define ls u << 1
#define rs (u << 1 | 1)
#define LL long long

const int N = 500010;

int n, m;
int a[N];

struct node {
    int l, r;
    LL sum, lmx, rmx, mx;
} tr[4 * N];

void pushup(node &T, const node &L, const node &R) {
    T.sum = L.sum + R.sum;
    T.mx = std::max(std::max(L.mx, R.mx), L.rmx + R.lmx);
    T.lmx = std::max(L.lmx, L.sum + R.lmx);
    T.rmx = std::max(R.rmx, R.sum + L.rmx);
}

void build(int u, int l, int r) {
    tr[u] = {l, r, a[l], a[l], a[l], a[l]};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(tr[u], tr[ls], tr[rs]);
}

void modify(int u, int x, LL c) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u] = {x, x, c, c, c, c};
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) modify(ls, x, c);
    else modify(rs, x, c);
    pushup(tr[u], tr[ls], tr[rs]);
}

node query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u];
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (r <= mid) return query(ls, l, r);
    if (l > mid) return query(rs, l, r);
    node T{};
    pushup(T, query(ls, l, mid), query(rs, mid + 1, r));
    return T;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int opt, l, r;
        std::cin >> opt >> l >> r;
        if (opt == 1) {
            if (l > r) std::swap(l, r);
            std::cout << query(1, l, r).mx << '\n';
        } else modify(1, l, r);
    }
    return 0;
}

区间gcd

懒标记

对于gcd(a , b) 存在一些性质，比如 gcd(a , b , c) = gcd(gcd(a , b) , c)
如果你对 gcd 不了解的话，请你看我的关于gcd 和 lcm 相关结论和性质的介绍。

那么这就是区间信息的维护，需要的话加上懒标记对吧，所以比较简单。

差分维护

我们介绍另外一种，比较简单的维护方法的。

  • 引入gcd性质

**即原序列的 gcd 也是差分的 gcd **

这种做法的延展性也非常好，直接维护序列差分信息。

  1. 求区间和 ，这个非常好求。前面讲过，只需要维护两棵线段树即可。
  2. 区间修改，差分的区间修改，只需要进行单点修改即可.
  3. 区间gcd 查询 ，这样求出即可。
    本人对于这种做法理解也不是特别深刻，建议去b站找相关视频再理解理解！
    哔哩哔哩

无法维护通过子节点维护区间信息的情况

一种做法 ：分块、莫队

另外一种可能的做法 ： 线段树

通过题目给出的一些信息也可以发现一些性质，从题设的性质出发，找到突破口。

P4145 上帝造题的七分钟 2 / 花神游历各国 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个题目需要发现一个性质：

  1. 题设给出数据范围最多 , 那么开方多少次就是1了呢（因为1开方不变）？
    image.png
    只需要6次开方就可以到1
    所以我们可以考虑直接暴力区间修改，序列中所有的数，每个数最多可以开方6次，那么意味着区间修改是常数级别的。总的时间复杂度还是 , 所以考虑直接暴力区修。
  2. 区间和， 每次区间修改之后，pushup维护区间和即可。

这里推荐董哓算法的讲解

总结

线段树，还支持其他非常多的操作，无法一一列举。原因有二 ，一是、太多操作无法一一列举，情况太多。二是 、 笔者本身实力有限，暂时无法介绍更加深入的运用。类似于zkw 线段树、区间众数，李超线段树、线段树分裂等等算法，还请读者自行了解！祝大家 RP++

赏

愿此行，终抵群星！