---
url: /algo/wtbuzpvk/index.md
---
## 引言

::: warning
本文如果不说明，那么所有数组都是 0--base。
:::

> *「线段树是算法竞赛中常用的用来维护区间信息的数据结构。」*

面对算法竞赛中的题目，如果看到区间修改与区间查询这几个字眼，那使用线段树是一个很不错的选择，它用分治(Divide and Conquer)的思想，用二叉搜索的方式将修改与查询的复杂度降低到 $O(\log n)$。

如要继续，建议先学会：二叉树存储，前缀和，如果你学会了树状数组那更好。

## 信息存储

对于多个信息同时存储，使用结构体或 class 是最好的选择；为了封装度，我们选择更好用的 class。

```cpp
class SegTree;

class SegTreeNode
{
public:
    SegTreeNode() = default;
    SegTreeNode(int nid) : id(nid), parent(nullptr), left(nullptr), right(nullptr) {}

private:
    int id;
    int l, r;
    SegTreeNode *parent;
    int self_sum_val = 0; // 区间信息，这里指的是 sum
    SegTreeNode *left;
    SegTreeNode *right;

    friend class SegTree;
};
```

## 线段树的构建

要知道如何构建线段树，得先知道线段树长啥样，准确来说，线段树是一个二叉树，且为满二叉树 \[+fullbt]。

\[+fullbt]:
Full Binary Tree，一个节点要么是叶子节点，要么有左右孩子。

每一个节点代表一个区间，其中树的末端的区间长度为 1，两个子节点的父节点维护这两个子节点的信息，例如可以是和，也可以是最大值，甚至可以是 xor，这里面我们使用一个数组来举例，令 $a\[7] = {1,3,5,3,7,2,8}$，那么顶端维护的数组信息 $\text{tree}\[0]$ 为所有长度的 $a$ 数组；在其子节点分裂成两份，若为偶数，则平分长度，否则左侧比右侧长度多1，那么下面这个图描述存储信息:

这样我们可以通过递归的方式从底向上到每个节点传递信息，这样就可以填充所有 tree 数组表，参考代码如下：

```cpp
class SegTree
{
public:
    SegTree(const vector<int> &v)
    {
        n = v.size();
        arr = v;
        nodes.resize(4 * n, nullptr);   // 线段树预先分配 4 个原数组大小 n 的空间
        root = build(0, n - 1, nullptr, 0);
    }

private:
    int n;
    SegTreeNode *root;
    vector<int> arr;
    vector<SegTreeNode *> nodes;
    SegTreeNode *build(int arrl, int arrr, SegTreeNode *parent, int cur_cnt)// [!code focus]
    {// [!code focus]
        SegTreeNode *node = new SegTreeNode(cur_cnt);// [!code focus]
        node->parent = parent;// [!code focus]
        node->l = arrl;// [!code focus]
        node->r = arrr;// [!code focus]

        if (arrl == arrr) // 叶子节点 // [!code focus]
        {// [!code focus]
            node->self_sum_val = arr[arrl];// [!code focus]
            node->left = node->right = nullptr;// [!code focus]
            nodes[cur_cnt] = node;// [!code focus]
            return node;// [!code focus]
        }// [!code focus]

        int mid = (arrl + arrr) / 2;// [!code focus]

        node->left = build(arrl, mid, node, 2 * cur_cnt + 1); // 左递归// [!code focus]
        node->right = build(mid + 1, arrr, node, 2 * cur_cnt + 2);// 右递归// [!code focus]

        node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;// [!code focus]
        nodes[cur_cnt] = node;// [!code focus]

        return node;// [!code focus]
    }// [!code focus]
};
```

此时我们可以根据 SegTree 实例中的 nodes 成员查看区间信息。

## 区间查询

如果需要查询区间，那就将其分为几个极大区间处理，例如计算区间 $a\[1,5]$ 的和，那么就有区间:
$$
a\[1,5]=a\[1]+a\[2,3]+a\[4,5]
$$
也就是说我们只需要返回所有覆盖区间的值即可。

```cpp
int query_sum(SegTreeNode *node, int ql, int qr)
{
    if (!node || qr < node->l || ql > node->r)
        return 0;  // 完全不相交

    if (ql <= node->l && node->r <= qr)
        return node->self_sum_val;  // 完全覆盖

    // 部分相交，递归左右子树
    return query_sum(node->left, ql, qr) + query_sum(node->right, ql, qr);
}
```

从图上来看，这就是线段树的查找路径，蓝色部分为完全覆盖到区间：

单点修改只需要一直传给 parent 即可。

```cpp
void point_set(int pos, int val)
{
    int pre = arr[pos];
    arr[pos] = val;
    int adds = val - pre;
    SegTreeNode *current = nodes[pos];
    while (current != nullptr)
    {
        current->self_sum_val += adds;
        current = current->parent;
    }
}
```

## 区间修改与懒标记

有同学说，如果到上面只需要单点修改，我还不如使用树状数组，常数小，代码短，那么线段树的优势就体现在快速区间修改上面。如果简单的对数组的每一个数进行修改，那么复杂度是 $O(n\log n)$，速度很慢，那么我们就有必要引入一个懒标记，等到需要更新的的时候我们再进行更新数组。

接下来我们会对上面已经实现的线段树进行大改，引入懒标记和标记信息：

```cpp
class SegTreeNode
{
public:
    SegTreeNode() = default;
    SegTreeNode(int nid) : id(nid), parent(nullptr), left(nullptr), right(nullptr) {}

private:
    int id;
    int l, r;
    SegTreeNode *parent;
    int self_sum_val = 0; 
    SegTreeNode *left;
    SegTreeNode *right;
    bool has_lazy = false;// [!code focus]
    int lazy_add_val = 0;// [!code focus]

    friend class SegTree;
};
```

然后我们讲一下原理，假设将 $\[3,5]$ 每个数值都加上 5，还是和刚刚一样自树根向下寻找极大覆盖区间，然后对这些区间打上懒标记。在递归向上传递的时候，顺带将路径上的所有值进行更新。如果是区间增加 $x$ 的话，那么 $lazy += x,sum+=len\times x$，如果是区间统一改成 $x$。那么 $lazy=x,sum=len\times x$，当计算到当前区间时，就向下传递懒标记。

下面图的蓝色部分表示搜索终点，即打上懒标记的点，紫色部分表示在递归过程中同步进行修改的节点（注意紫色部分无需懒标记）

当等到要查询的时候，如果当前递归访问的节点已经产生懒标记，就将懒标记向下推：我们举个例子：如果是将 $\[3,5]$ 每个数值都加上 5 后计算 $a\[0,6]$，在打懒标记查询极大区间的时候，我们在递归的时候就向上传递了信息此时无需向下传递懒标记，直接返回 $\text{tree}\[0]$ 就是结果。

那如果我们查询的是 $a\[1,4]$，其极大区间表示为:
$$
a\[1,4] = a\[1]+a\[2,3]+a\[4]
$$
其中递归到 $a\[4]$ 部分首先需要先递归到 $a\[4,5]$，但 $a\[4,5]$ 又有懒标记，所以我们在处理 $a\[4,5]$ 的时候，将懒标记下传到 $a\[4]$ 和 $a\[5]$，即如图所示：

然后在计算 $a\[4]$，继续下传，将懒标记的值加到自身，由于已经到低了，所以直接丢弃懒标记，此时懒标记只剩 $a\[5]$ 有 $+5$ 懒标记。

这里我们代码以区间加为例，首先还是一样，递归查找极大覆盖区间：

```cpp
void range_add_impl(SegTreeNode *node, int ql, int qr, int val)
{
    if (!node || qr < node->l || ql > node->r)
        return; // 不相交

    if (ql <= node->l && node->r <= qr)
    {
        // 完全覆盖
        node->self_sum_val += val * (node->r - node->l + 1);
        node->lazy_add_val += val;
        node->has_lazy = true;
        return;
    }

    // 继续递归前先下推懒标记信息
    push_down(node);

    range_add_impl(node->left, ql, qr, val);
    range_add_impl(node->right, ql, qr, val);

    node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;
}
```

向下推懒标记：

```cpp
void push_down(SegTreeNode *node)
{
    if (!node || !node->has_lazy || node->l == node->r)
        return;

    int add = node->lazy_add_val;

    // 左儿子
    node->left->self_sum_val += add * (node->left->r - node->left->l + 1);
    node->left->lazy_add_val += add;
    node->left->has_lazy = true;

    // 右儿子
    node->right->self_sum_val += add * (node->right->r - node->right->l + 1);
    node->right->lazy_add_val += add;
    node->right->has_lazy = true;

    // 清空当前节点懒标记
    node->lazy_add_val = 0;
    node->has_lazy = false;
}
```

这样一个基础的区间修改，求和的线段树模板封装完毕！

## Full Code

```cpp :collapsed-lines
#include <bits/stdc++.h>
using namespace std;

class SegTree;

class SegTreeNode
{
public:
    SegTreeNode() = default;
    SegTreeNode(int nid) : id(nid), parent(nullptr), left(nullptr), right(nullptr) {}

private:
    int id;
    int l, r;
    SegTreeNode *parent;
    int self_sum_val = 0; // 区间信息，这里指的是 sum
    SegTreeNode *left;
    SegTreeNode *right;
    bool has_lazy = false;
    int lazy_add_val = 0;

    friend class SegTree;
};

class SegTree
{
public:
    SegTree(const vector<int> &v)
    {
        n = v.size();
        arr = v;
        nodes.resize(4 * n, nullptr);
        root = build(0, n - 1, nullptr, 0);
    }
    int range_sum(int l, int r) { return query_sum(root, l, r); }
    void range_add(int l, int r, int val) { range_add_impl(root, l, r, val); }

private:
    int n;
    SegTreeNode *root;
    vector<int> arr;
    vector<SegTreeNode *> nodes;

    SegTreeNode *build(int arrl, int arrr, SegTreeNode *parent, int cur_cnt)
    {
        SegTreeNode *node = new SegTreeNode(cur_cnt);
        node->parent = parent;
        node->l = arrl;
        node->r = arrr;

        if (arrl == arrr) // 叶子节点
        {
            node->self_sum_val = arr[arrl];
            node->left = node->right = nullptr;
            nodes[cur_cnt] = node;
            return node;
        }

        int mid = (arrl + arrr) / 2;

        node->left = build(arrl, mid, node, 2 * cur_cnt + 1);
        node->right = build(mid + 1, arrr, node, 2 * cur_cnt + 2);

        node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;
        nodes[cur_cnt] = node;

        return node;
    }
    int query_sum(SegTreeNode *node, int ql, int qr)
    {
        if (!node || qr < node->l || ql > node->r)
            return 0; // 完全不相交

        if (ql <= node->l && node->r <= qr)
            return node->self_sum_val; // 完全覆盖

        // 部分相交，递归左右子树
        return query_sum(node->left, ql, qr) + query_sum(node->right, ql, qr);
    }

    void range_add_impl(SegTreeNode *node, int ql, int qr, int val)
    {
        if (!node || qr < node->l || ql > node->r)
            return; // 不相交

        if (ql <= node->l && node->r <= qr)
        {
            node->self_sum_val += val * (node->r - node->l + 1);
            node->lazy_add_val += val;
            node->has_lazy = true;
            return;
        }

        // 继续递归前先下推
        push_down(node);

        range_add_impl(node->left, ql, qr, val);
        range_add_impl(node->right, ql, qr, val);

        node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;
    }

    void push_down(SegTreeNode *node)
    {
        if (!node || !node->has_lazy || node->l == node->r)
            return;

        int add = node->lazy_add_val;

        // 左儿子
        node->left->self_sum_val += add * (node->left->r - node->left->l + 1);
        node->left->lazy_add_val += add;
        node->left->has_lazy = true;

        // 右儿子
        node->right->self_sum_val += add * (node->right->r - node->right->l + 1);
        node->right->lazy_add_val += add;
        node->right->has_lazy = true;

        // 清空当前节点懒标记
        node->lazy_add_val = 0;
        node->has_lazy = false;
    }
};
```