线段树

本文大部分内容来自 LFool⚡ 的力扣题解：https://leetcode.cn/problems/my-calendar-ii/solution/by-lfool-nodi/

另外小部分参考线段树 -- 新手篇

0. 定义

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点，对于线段树中的每一个非叶子节点 [a, b], 它的左儿子表示的区间为 [a, (a+b)/2], 右儿子表示的区间为 [(a+b)/2+1, b]。因此线段树是平衡二叉树，最后的子节点数目为 N，即为整个线段区间的长度。

使用线段树可以快速的查找一个节点在若干条线段中出现的次数，时间复杂度为 O(logN)，而未优化的空间复杂度为 2N，因此有时需要离散化让空间压缩

线段树解决的是「区间和」问题，并且该「区间」会被修改。例如对于一个数组，多次求某个区间的和，可以使用「前缀和」实现，但是如果区间里面的元素经常变化时「前缀和」的效率就没那么高效。为此引入线段树，线段树中的每个节点代表一个区间，对于数组 nums=[1, 2, 3, 4, 5] 对应的线段树为：

说明：

每个节点代表一个区间，节点的值就是该区间的和
节点的值可以根据题目要求换成自己满足 「区间加法」 的表示，例如
- 最大公因数 GCD：总GCD = gcd (左区间GCD，右区间GCD)
- 最大值：总最大值 = max (左区间最大值，右区间最大值)
有些不符合 「区间加法」 的表示需要注意，例如：
- 众数：根据左右区间的众数不能求出总区间的众数
- 01序列的最长连续零：根据左右区间的最长连续零，没法知道总的最长连续零
根节点代表的区间是问题的总区间，例如上图中数据的长度就是 [0, 4]
线段树是一棵近似的完全二叉树，如上图，但也有不是完全二叉树的情况
建立线段树的过程就是不断把区间 「平分」 的过程，直到区间长度为1

1. 基本操作

数据结构：由于线段树是一棵近似的完全二叉树，因此可以使用二叉树的结构表示

class Node
{
    int val;           // 当前节点值
    Node *left, *right; // 左右孩子节点
    Node(int a = 0) : val(a), left(nullptr), right(nullptr){};
    ~Node()
    {
        delete left;
        delete right;
    }
}

建立线段树

如果题目中给了具体的区间范围，我们可以根据范围建立线段树

void buildTree(Node *node, int start, int end)
{
    // 到达叶子节点
    if (start == end)
    {
        node->val = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    buildTree(node->left, start, mid);
    buildTree(node->right, mid + 1, end);

    // 向上更新
    pushUp(node);
}

void pushUp(Node *node)
{
    node->val = node->left->val + node->right->val;
}

对于没有具体范围的情况，一般只有数据的取值范围，一般都很大，可以使用 「动态开点」 ，例如刚开始我们只知道数组的长度为5，不知道数组内每个元素的大小，元素都是一个一个添加进去的，此时需要动态开点，例如刚开始的节点就只能是 [0, 4]; val = 0，此时添加元素 [2, 2]; val = 3，线段树变为：

这里需要解释一下，如果一个节点没有左右孩子，会一下子把左右孩子节点都给创建出来，如上图橙色节点所示，具体代码可见方法 pushDown()

两个橙色的叶子节点仅仅只是被创建出来了，并无实际的值，均为 0；而另外一个橙色的非叶子节点，值为 3 的原因是下面的孩子节点的值向上更新得到的

下面给出依次添加剩余节点的过程：(注意观察值的变化！！)

「动态开点」一般是在「更新」或「查询」的时候动态的建立节点，具体可见下面的更新和查询操作

更新线段树：将指定区间如 [2, 4] 的元素都增加1

更新的前提是查询需要更新的区间，首先查找到区间 [2, 2] 和 [3, 4]，然后更新节点，但是如果只是更新这两个节点的话也有问题，因为 [3, 3] 和 [4, 4] 也需要更新，当查询它们时才可以得到更新之后的值。

为此，我们给节点添加一个「懒惰标记」，给更新区间的对应节点添加一个懒惰标记，表示该节点所有对应的孩子节点都应该有此次更新，当向孩子节点遍历的时候会把「懒惰标记」下推给孩子节点，如果节点不存在最优孩子节点时需要创建左右孩子节点，最终我们修改 Node 的数据结构：

class Node
{
    int val;           // 当前节点值
    int lazy;          // 添加的懒惰标记
    Node *left, *right; // 左右孩子节点
    Node(int a = 0) : val(a), left(nullptr), right(nullptr){};
    ~Node()
    {
        delete left;
        delete right;
    }
}

『下推懒惰标记』函数：

// leftNum 和 rightNum 表示左右孩子区间的叶子节点数量
void pushDown(Node *node, int leftNum, int rightNum)
{
    if (node->left == nullptr)
        node->left = new Node();
    if (node->right == nullptr)
        node->right = new Node();

    // 没有标记直接返回
    if (node->lazy == 0)
        return;
    // 如果是「加减」更新操作就需要使用：标记值 * 子树所有叶子节点数量
    node->left->val += node->lazy * leftNum;
    node->right->val += node->lazy * rightNum;
    // 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
    node->left->lazy += node->lazy;
    node->right->lazy += node->lazy;
    // 取消当前节点的标记
    node->lazy = 0;
}

「更新最终函数」：

// 在 start...end 范围内更新 l...r 区间中的每个元素，都加 val
void update(Node *node, int start, int end, int l, int r, int val)
{
    // 找到满足要求的区间
    if (l <= start && end <= r)
    {
        // 区间节点加上子树所有叶子节点
        node->val += (end - start + 1) * val;
        // 累计添加懒惰标记
        node->lazy += val;
        return;
    }
    int mid = (start + end) / 2;
    // 下推标记，mid - start + 1 表示左孩子区间叶子节点数量，end - mid 表示右孩子区间叶子节点数量
    pushDown(node, mid - start + 1, end - mid);
    if (l <= mid)
        update(node->left, start, mid, l, r, val);
    if (r > mid)
        update(node->right, mid + 1, end, l, r, val);
    // 向上更新
    pushUp(node);
}

查询线段树：查询某一个区间如 [2, 4] 的结果（图中红色标记）并返回

// 在区间 [start, end] 中查询区间 [l, r] 的结果，注意 [l, r] 保持不变
int query(Node *node, int start, int end, int l, int r)
{
    // 区间 [l ,r] 完全包含区间 [start, end]
    // 例如：[2, 4] = [2, 2] + [3, 4]，当 [start, end] = [2, 2] 或者 [start, end] = [3, 4]，直接返回
    if (l <= start && end <= r)
    {
        return node->val;
    }

    // 把当前区间 [start, end] 均分得到左右孩子的区间范围
    // node 左孩子区间 [start, mid]
    // node 左孩子区间 [mid + 1, end]
    int mid = (start + end) / 2;
    int ans = 0;
    pushDown(node, mid - start + 1, end - mid);
    if (l <= mid)
    {
        ans += query(node, start, mid, l, r);
    }
    if (r > mid)
    {
        ans += query(node->right, mid + 1, end, l, r);
    }
    return ans;
}

2. 完整模板

基于求「区间和」以及对区间进行「加减」的更新操作的常规模板

// 线段树代码
#include <iostream>
#include <vector>
using namespace std;

// node_idx 为线段树下标，从1开始取
void build_tree(vector<int>& arr, vector<int>& tree, int start, int end, int node_idx)
{
    //递归的出口，也就是到了叶子节点
    if(start == end) {
        tree[node_idx] = arr[start];
    } else {
        //找到左子树的节点(2*node_idx)
        //找到右子树的节点(2*node_idx+1)
        int left_node = 2*node_idx, right_node = 2*node_idx + 1;
        int mid = (start + end) / 2;
        //将树进行分割，然后左右递归建树
        build_tree(arr, tree, start, mid, left_node);
        build_tree(arr, tree, mid+1, end, right_node);
        tree[node_idx] = tree[left_node] + tree[right_node];
    }
}

// 查询 [l, r] 的区间和，node_idx 从1开始
int query(vector<int>& arr, vector<int>& tree, int start, int end, int l, int r, int node_idx)
{
    //情况一
    if(l > end || r < start) {
        return 0;
    } else if (l <= start && end <= r) { //情况二
        return tree[node_idx];
    } else {
        //递归查询
        //找到左子树的节点(2*node_idx)
        //找到右子树的节点(2*node_idx+1)
        int left_node = 2*node_idx, right_node = 2*node_idx + 1;
        int mid = (start + end) / 2;
        //将树进行分割，然后左右递归查询
        int left_sum = query(arr, tree, start, mid, l, r, left_node);
        int right_sum = query(arr, tree, mid+1, end, l, r, right_node);
        return left_sum + right_sum;
    }
}

// 更新指定下标 update_idx 的元素，node_idx 从1开始取
void update(vector<int>& arr, vector<int>& tree, int start, int end, int node_idx, int update_idx, int val)
{
    //递归的出口，也就是到了叶子节点, 更新其值
    if(start == end) {
        tree[node_idx] = arr[start] = val;
    } else {
        //找到左子树的节点(2*node_idx)
        //找到右子树的节点(2*node_idx+1)
        int left_node = 2*node_idx, right_node = 2*node_idx + 1;
        int mid = (start + end) / 2;
        //如果要更新节点在右边
        if(update_idx > mid) {
            update(arr, tree, mid+1, end, right_node, update_idx, val);
        } else { //要更新节点在左边
            update(arr, tree, start, mid, left_node, update_idx, val);
        }
        //要注意更新当前节点！！！！！！
        tree[node_idx] = tree[left_node] + tree[right_node];
    }
}

int main()
{
    vector<int> arr = {93, 90, 50, 50, 1};
    int n = arr.size();
    vector<int> tree(4*n);
    build_tree(arr, tree, 0, n-1, 1);
    cout << "更新前的树:";
    for (auto& x : tree) cout << x << " ";
    cout << endl;
    
    //更新 idx = 4的元素值为 2
    update(arr, tree, 0, n-1, 1, 4, 2);
    cout << "更新后的树:";
    for (auto& x : tree) cout << x << " ";
    cout << endl;
    
    cout << "查询区间[2,4]的和为：" << query(arr, tree, 0, n-1, 2, 4, 1) << endl;

    return 0;
}

基于求「区间和」以及对区间进行「加减」的更新操作，且为「动态开点」的模板

struct Node
{
    int lazy;
    int val;
    Node *left;
    Node *right;
    Node(int a = 0) : val(a), lazy(0), left(nullptr), right(nullptr){};
};

class SegmentTree
{
private:
    Node *root;

public:
    SegmentTree()
    {
        root = new Node();
    }

    // 更新 [l, r] 区间里面元素
    void update(Node *node, int start, int end, int l, int r, int val)
    {
        if (l <= start && end <= r)
        {
            node->val += (end - start + 1) * val;
            node->lazy += val;
            return;
        }

        int mid = (start + end) / 2;
        // 下推懒惰标记
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid)
            update(node->left, start, mid, l, r, val);
        if (r > mid)
            update(node->right, mid + 1, end, l, r, val);
        pushUp(node);
    }

    int query(Node *node, int start, int end, int l, int r)
    {
        if (l <= start && end <= r)
            return node->val;
        int mid = (start + end) / 2;
        int ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid)
            ans += query(node->left, start, mid, l, r);
        if (r > mid)
            ans += query(node->right, mid + 1, end, l, r);
        return ans;
    }

    void pushDown(Node *node, int leftNum, int rightNum)
    {
        if (node->left == nullptr)
            node->left = new Node();
        if (node->right == nullptr)
            node->right = new Node();

        if (node->lazy == 0)
            return;
        node->left->val += node->lazy * leftNum;
        node->right->val += node->lazy * rightNum;

        // 更新懒惰标记
        node->left->lazy += node->lazy;
        node->right->lazy += node->lazy;
        node->lazy = 0;
    }

    // 这里如果不是维护区间和需要注意改变
    void pushUp(Node *node)
    {
        node->val = node->left->val + node->right->val;
    }
};

3. 常见题型

题目	说明	题解
729. 我的日程安排表 I	维护区间最值并对区间进行加减更新，暴力维护，差分数组	解
731. 我的日程安排表 II	维护区间最值并对区间进行加减更新，暴力维护，差分数组	解
732. 我的日程安排表 III	维护区间最值并对区间进行加减更新，差分数组	解
307. 区域和检索 - 数组可修改	维护区间和并对区间进行覆盖更新，参考题解的第二份cpp代码	解
933. 最近的请求次数	维护区间和并对区间进行加减更新，直接队列就可以	解

对于表示为 「区间和」 且对区间进行 「加减」 的更新操作的情况，我们在更新节点值的时候『需要✖️左右孩子区间叶子节点的数量 (注意是叶子节点的数量)』；我们在下推懒惰标记的时候『需要累加』！！(这种情况和模版一致！！) 如题目 933.最近的请求次数
对于表示为 「区间和」 且对区间进行 「覆盖」 的更新操作的情况，我们在更新节点值的时候『需要✖️左右孩子区间叶子节点的数量 (注意是叶子节点的数量)』；我们在下推懒惰标记的时候『不需要累加』！！(因为是覆盖操作！！) 如题目 307.区域和检索 - 数组可修改
对于表示为 「区间最值」 且对区间进行 「加减」 的更新操作的情况，我们在更新节点值的时候『不需要✖️左右孩子区间叶子节点的数量 (注意是叶子节点的数量)』；我们在下推懒惰标记的时候『需要累加』！！如题目 729.我的日程安排表 I、732.我的日程安排表 III

注意：对于题目最近的请求次数和区域和检索 - 数组可修改可以「不用✖️左右孩子区间叶子节点的数量」

因为这两个题目是「点更新」，「点更新」和「区间更新」可以合并成一种，「点更新」就是更新长度为 1 的「区间更新」

4. 总结

线段数在多次求取「区间和」问题上具有优势，但是实际面试比较难想出来，而且实际体型中使用常规的方法如暴力维护、差分数组等可能比直接维护 [0, 1e9] 上的线段树时间复杂度低，因此这个数据结构先简单了解就好，具体熟练掌握可能有点难度。

面试中可能很难写出完整线段树，所以这类题如果可以使用差分数组的话尽量直接用差分数组来写，再不济暴力维护也不是不行

5. 参考

线段树详解「汇总级别整理 🔥🔥🔥」
小虎：线段树 -- 新手篇

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

线段树.md

线段树.md

线段树

0. 定义

1. 基本操作

2. 完整模板

3. 常见题型

4. 总结

5. 参考

Files

线段树.md

Latest commit

History

线段树.md

File metadata and controls

线段树

0. 定义

1. 基本操作

2. 完整模板

3. 常见题型

4. 总结

5. 参考