当前位置：网站首页>(线段树) 基础线段树常见问题总结

(线段树) 基础线段树常见问题总结

2022-07-31 03:20:00 【天赐细莲】

文章目录

前言
完整例题
END

前言

线段树的名声，想必不会写的也听过名字，已成为算法选手的基本技能之一。

线段树的难点不在什么三件套递归的编写，怎么划分mid的左右，怎么动态开点，这些都很模板

真正的难点在于如何根据需求构造和处理pushUp()和pushDown()

线段树也有很多衍生操作，如珂朵莉树，主席树等等

本文只设计基本的线段树操作，其中带一些动态开点，树链剖分等，但这些不是重点(因为找不到纯模板题)，重点的构造的类型

本文重点在于如何确定需求，如何构造pushUp()和pushDown()

笔者线段树的题刷的比较少，但还是总结出了一些常见构造类型

如：区间加乘，区间覆盖，区间bool标记等

区间求和，区间计数，区间求最值等

完整例题

单点加值区间求和

例题：洛谷：P3374 【模板】树状数组 1
练习题：
力扣：307. 区域和检索 - 数组可修改

构造目标：
单点加值区间求和
实现思路：
这种类型是非常基本的线段树，当left和right相同时，就是目标的点，直接累加
然后求和只要将root<<1和root<<1|1两个子树的值的和存储在父节点即可
这里再update和query中主要展示两种写法
根据mid判断左右的递归方向
在函数开头判断区间合法性，二分后直接递归
本文后面主要用第二种方式展示

/** * P3374 【模板】树状数组 1 * https://www.luogu.com.cn/problem/P3374 */
#include <bits/stdc++.h>
using namespace std;

struct SegTreeNode {
    
    int val = 0;
};

vector<SegTreeNode> segTree;
vector<int> arr;

inline void pushUp(int root) {
    
    segTree[root].val = segTree[root << 1].val + segTree[root << 1 | 1].val;
}

void build(int root, int left, int right) {
    
    if (left == right) {
    
        segTree[root].val = arr[left];
        return;
    }

    int mid = left + (right - left) / 2;
    build(root << 1, left, mid);
    build(root << 1 | 1, mid + 1, right);

    pushUp(root);
}

void update(int root, int left, int right, int cur, int val) {
    
    if (left == right) {
    
        segTree[root].val += val;
        return;
    }

    int mid = (right - left) / 2 + left;
    if (cur <= mid) {
    
        update(root << 1, left, mid, cur, val);
    } else {
    
        update(root << 1 | 1, mid + 1, right, cur, val);
    }
    pushUp(root);
}

int query(int root, int left, int right, int from, int to) {
    
    // 两个区间无重合
    if (from > right || to < left) {
    
        return 0;
    }
    // 完全包含
    if (from <= left && to >= right) {
    
        return segTree[root].val;
    }

    int mid = (right - left) / 2 + left;

    // int ans = 0;
    // if (from <= mid) {
    
    // ans += query(root << 1, left, mid, from, to);
    // }
    // if (to >= mid+1) {
    
    // ans += query(root << 1 | 1, mid + 1, right, from, to);
    // }
    // return ans;

    return query(root << 1, left, mid, from, to) +
           query(root << 1 | 1, mid + 1, right, from, to);
}

int main() {
    
    int n, m;
    cin >> n >> m;

    segTree.resize(n << 2);
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++) {
    
        cin >> arr[i];
    }

    build(1, 1, n);

    while (m--) {
    
        int ask, idx, val, from, to;
        cin >> ask;
        if (ask == 1) {
    
            cin >> idx >> val;
            update(idx, val, 1, n, 1);
        } else {
    
            cin >> from >> to;
            cout << query(from, to, 1, n, 1) << endl;
        }
    }

    return 0;
}

单点覆盖区间求最值

例题：洛谷：P1531 I Hate It
杭电：I Hate It - 1754
这两题算法完全一样，但我在杭电用cin没过，洛谷用scanf没过。。。

构造目标：
单点覆盖区间求最值
实现思路：
覆盖那就直接把值等于上去即可
单点型也没必要用上lazy标记，因为这是直接作用于某个点，没有范围可言
本题主要想表示的是，单点型也可以写成区间的形式
只要在调用的时候，让询问的左右区间是同一个点即可
即：区间夹击成一个点

/** * 洛谷：P1531 I Hate It * https://www.luogu.com.cn/problem/P1531 * 单点修改， 区间查询最大值 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define ls (root << 1)
#define rs (root << 1 | 1)

const int M = 10 + 200000;
struct SegTreeNode {
    
    int val;  // 最值
};

SegTreeNode segTree[M << 2];
int arr[M];

void pushUp(int root) {
    
    segTree[root].val = max(segTree[ls].val, segTree[rs].val);
}

void build(int root, int left, int right) {
    
    if (left == right) {
    
        segTree[root].val = arr[left];
        return;
    }
    int mid = (right - left) / 2 + left;
    build(ls, left, mid);
    build(rs, mid + 1, right);
    pushUp(root);
}

void update(int root, int left, int right, int from, int to, int val) {
    
    if (from > right || to < left) {
    
        return;
    }
    // 简单覆盖类可以不用不用lazy
    if (from <= left && right <= to) {
    
        segTree[root].val = val;
        return;
    }
    int mid = (right - left) / 2 + left;
    update(ls, left, mid, from, to, val);
    update(rs, mid + 1, right, from, to, val);
    pushUp(root);
}

int query(int root, int left, int right, int from, int to) {
    
    if (from > right || to < left) {
    
        return 0;
    }
    if (from <= left && right <= to) {
    
        return segTree[root].val;
    }
    int mid = (right - left) / 2 + left;
    return max(query(ls, left, mid, from, to),
               query(rs, mid + 1, right, from, to));
}

signed main(void) {
    
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    
        cin >> arr[i];
    }

    build(1, 1, n);

    while (m--) {
    
        char ch;
        cin >> ch;

        if (ch == 'Q') {
    
            int from, to;
            cin >> from >> to;
            cout << query(1, 1, n, from, to) << endl;
        } else {
    
            int idx, val;
            cin >> idx >> val;
            int pre = query(1, 1, n, idx, idx);
            if (pre < val) {
    
                update(1, 1, n, idx, idx, val);
            }
        }
    }

    return 0;
}

区间加值区间求和 (树链剖分完整版)

例题：洛谷：P3384 【模板】轻重链剖分/树链剖分

构造目标：
区间加值区间求和
实现思路：
本题的核心在与如何把单个val加入到一个区间的每个数字中
我们知道一个root代表一个区间，区间就有长度；
那只需把val * length(root的区间) 即可；
可以理解为改区间里的每个点都有一个贡献的val，n个val相加，那就是n*val
同理，在pushDown()的时候也要计算该父节点对应左右孩子的长度；
因此，这里的pushDown()还需要传入左右点的位置
对真正的区间操作就需要用到懒惰标记了
懒惰标记的作用在于多次更新，少量查询
就是在update()的时候先暂缓的记下来，最后query的时候一口气作用出来
树链剖分 (非本文重点)
这份代码还是树链剖分的完整模板
先后调用两个dfs求出一对目标数组
在根据求lca的性质作用在线段树上
两点间更新，两点间查询
子树更新，子树查询

/** * P3384 【模板】轻重链剖分树链剖分 * https://www.luogu.com.cn/problem/P3384 */
#include <bits/stdc++.h>
#define int long long
using namespace std;

#define ls (root << 1)
#define rs (root << 1 | 1)

const int M = 10 + 1 * 100000;
static int mod = 1e9 + 7;  // 不用const 手动输入
int n;                     // 数据范围
/** ******************************************************************/

vector<int> oldVal(M);  // 点权的初始值
vector<int> newVal(M);  // 剖分后对应的值
/** ******************************************************************/

// 线段树模板
struct SegTreeNode {
    
    int val;
    int lazy;
};
vector<SegTreeNode> segTree(M << 2);

void pushUp(int root) {
    
    segTree[root].val = (segTree[ls].val + segTree[rs].val) % mod;
}

void pushDown(int root, int left, int right) {
    
    int mid = left + (right - left) / 2;
    int leftLen = mid - left + 1;
    int rightLen = right - mid;
    if (segTree[root].lazy != 0) {
    
        // val 累计lazy*len
        segTree[ls].val =
            (segTree[ls].val + segTree[root].lazy * leftLen) % mod;
        segTree[rs].val =
            (segTree[rs].val + segTree[root].lazy * rightLen) % mod;
        // lazy 直接累计
        segTree[ls].lazy = (segTree[ls].lazy + segTree[root].lazy) % mod;
        segTree[rs].lazy = (segTree[rs].lazy + segTree[root].lazy) % mod;

        segTree[root].lazy = 0;
    }
}

void build(int root, int left, int right) {
    
    segTree[root].lazy = 0;
    if (left == right) {
    
        segTree[root].val = newVal[left];
        return;
    }
    int mid = left + (right - left) / 2;
    build(ls, left, mid);
    build(rs, mid + 1, right);
    pushUp(root);
}

void update(int root, int left, int right, int from, int to, int val) {
    
    if (from > right || to < left) {
    
        return;
    }
    if (from <= left && right <= to) {
    
        segTree[root].val =
            (segTree[root].val + val * (right - left + 1)) % mod;
        segTree[root].lazy = (segTree[root].lazy + val) % mod;
        return;
    }
    pushDown(root, left, right);
    int mid = left + (right - left) / 2;
    update(ls, left, mid, from, to, val);
    update(rs, mid + 1, right, from, to, val);
    pushUp(root);
}

int query(int root, int left, int right, int from, int to) {
    
    if (from > right || to < left) {
    
        return 0;
    }
    if (from <= left && right <= to) {
    
        return segTree[root].val;
    }
    pushDown(root, left, right);
    int mid = left + (right - left) / 2;
    return (query(ls, left, mid, from, to) +
            query(rs, mid + 1, right, from, to)) %
           mod;
}
/** ******************************************************************/

// 树链剖分模板
vector<vector<int>> graph(M);  // 图
vector<int> father(M);         // 父节点
vector<int> son(M);            // 重孩子
vector<int> size(M);           // 子树节点个数
vector<int> deep(M);           // 深度，根节点为1
vector<int> top(M);            // 重链的头，祖宗
vector<int> id(M);             // 剖分新id
int cnt = 0;                   // 剖分计数

void dfs1(int cur, int from) {
    
    deep[cur] = deep[from] + 1;  // 深度，从来向转化来
    father[cur] = from;          // 父节点，记录来向
    size[cur] = 1;               // 子树的节点数量
    son[cur] = 0;                // 重孩子 (先默认0表示无)
    for (int& to : graph[cur]) {
    
        if (to == from) {
      // 避免环
            continue;
        }
        dfs1(to, cur);                    // 处理子节点
        size[cur] += size[to];            // 节点数量叠加
        if (size[son[cur]] < size[to]) {
      // 松弛操作，更新重孩子
            son[cur] = to;
        }
    }
}

void dfs2(int cur, int grandfather) {
    
    top[cur] = grandfather;     // top记录祖先
    id[cur] = ++cnt;            // 记录剖分id
    newVal[cnt] = oldVal[cur];  // 映射到新值
    if (son[cur] != 0) {
            // 优先dfs重儿子
        dfs2(son[cur], grandfather);
    }
    for (int& to : graph[cur]) {
    
        if (to == father[cur] || to == son[cur]) {
    
            continue;  // 不是cur的父节点，不是重孩子
        }
        dfs2(to, to);  // dfs轻孩子
    }
}

// 本题中未使用
int lca(int x, int y) {
    
    while (top[x] != top[y]) {
      // 直到top祖宗想等
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);  // 比较top祖先的深度，x始终设定为更深的
        }
        x = father[top[x]];  // 直接跳到top的父节点
    }
    return deep[x] < deep[y] ? x : y;  // 在同一个重链中，深度更小的则为祖宗
}
/** ******************************************************************/

void updatePath(int x, int y, int val) {
    
    while (top[x] != top[y]) {
    
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);
        }
        update(1, 1, n, id[top[x]], id[x], val);
        x = father[top[x]];
    }
    if (deep[x] < deep[y]) {
    
        swap(x, y);
    }
    update(1, 1, n, id[y], id[x], val);
}

void updateTree(int root, int val) {
    
    update(1, 1, n, id[root], id[root] + size[root] - 1, val);
}

int queryPath(int x, int y) {
    
    int sum = 0;
    while (top[x] != top[y]) {
    
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);
        }
        sum += query(1, 1, n, id[top[x]], id[x]);
        sum %= mod;
        x = father[top[x]];
    }
    if (deep[x] < deep[y]) {
    
        swap(x, y);
    }
    sum += query(1, 1, n, id[y], id[x]);
    return sum % mod;
}

int queryTree(int root) {
    
    return query(1, 1, n, id[root], id[root] + size[root] - 1);
}
/** ******************************************************************/

signed main() {
    
    int m, root;
    cin >> n >> m >> root >> mod;

    for (int i = 1; i <= n; i++) {
    
        cin >> oldVal[i];
    }

    // 该树编号 [1, n]
    // 本题仅仅说有边，未说方向
    for (int i = 1, u, v; i <= n - 1; i++) {
    
        cin >> u >> v;
        graph[v].emplace_back(u);
        graph[u].emplace_back(v);
    }

    // 树链剖分 重链
    dfs1(root, 0);
    dfs2(root, root);
    // 根据映射的newVal建树
    build(1, 1, n);

    for (int i = 1, ask; i <= m; i++) {
    
        cin >> ask;
        int from, to, val, from, to, subtree;
        if (ask == 1) {
    
            cin >> from >> to >> val;
            updatePath(from, to, val);
        } else if (ask == 2) {
    
            cin >> from >> to;
            cout << queryPath(from, to) % mod << endl;
        } else if (ask == 3) {
    
            cin >> subtree >> val;
            updateTree(subtree, val);
        } else {
    
            cin >> subtree;
            cout << queryTree(subtree) % mod << endl;
        }
    }

    return 0;
}

区间加乘区间求和

例题：洛谷：P3373 【模板】线段树 2

构造目标：
多状态更新
区间加乘区间求和
实现思路：
根据每个状态，分别设定一个lazy，分别编写对应的update()
根据群论的知识(常识)可得
int lazyAdd = 0; // 加法
int lazyMul = 1; // 乘法
加法的更新在前面的例题中有介绍，就是根据区间长度来计算
这里主要讲下乘法的更新
从对单个点的作用到区间的思路来看；
x1 * val + x2 * val +...+xn * val 提取出val可化简得 sum(xi) * val
懒惰标记同理
注意因为乘法比加法高级，因此在乘法的的更新中也要作用到加法的lazy中
理解：val 的实际值应该是 (oldval + add)
有乘法后应该是 (oldval + add) * mul
根据乘法分配律 (oldval + add) * mul = oldval * mul + add * mul
而加法中 (oldval * mul) + add != (oldval + add) * (mul + add)
在pushDown()中
val 要同时根据add和mul更新
mul 不受 add影响
add 受 mul影响
这里再强调下pushDown的理念，这是自顶向下更新
是root 的内容对 ls 和 rs的修改作用，大范围区间影响到其子区间

/** * P3373 【模板】线段树 2 * https://www.luogu.com.cn/problem/P3373 * 区间修改(加法，乘法) 区间查询 */
#include <bits/stdc++.h>
#define int long long
using namespace std;

#define ls (root << 1)
#define rs (root << 1 | 1)

struct SegTreeNode {
    
    int val;
    int lazyAdd = 0;  // 加法
    int lazyMul = 1;  // 乘法
};
int mod;

vector<SegTreeNode> segTree;
vector<int> arr;

// 自底向上更新
inline void pushUp(int root) {
    
    segTree[root].val = (segTree[ls].val + segTree[rs].val) % mod;
}
// 自顶向下更新
inline void pushDown(int root, int left, int right) {
    
    int mid = (right - left) / 2 + left;
    int leftLen = mid - left + 1;
    int rightLen = right - mid;
    // 基于一些题目的特殊情况，这里最好判断一下懒惰标记
    segTree[ls].val = (segTree[ls].val * segTree[root].lazyMul +
                       segTree[root].lazyAdd * leftLen) %
                      mod;
    segTree[rs].val = (segTree[rs].val * segTree[root].lazyMul +
                       segTree[root].lazyAdd * rightLen) %
                      mod;

    segTree[ls].lazyMul = (segTree[ls].lazyMul * segTree[root].lazyMul) % mod;
    segTree[rs].lazyMul = (segTree[rs].lazyMul * segTree[root].lazyMul) % mod;

    segTree[ls].lazyAdd =
        (segTree[ls].lazyAdd * segTree[root].lazyMul + segTree[root].lazyAdd) %
        mod;
    segTree[rs].lazyAdd =
        (segTree[rs].lazyAdd * segTree[root].lazyMul + segTree[root].lazyAdd) %
        mod;

    segTree[root].lazyAdd = 0;
    segTree[root].lazyMul = 1;
}

// 建树
void build(int root, int left, int right) {
    
    // 初始化懒惰标记 加法为0 乘法为1
    segTree[root].lazyAdd = 0;
    segTree[root].lazyMul = 1;
    if (left == right) {
    
        segTree[root].val = arr[left] % mod;
        return;
    }

    int mid = (right - left) / 2 + left;
    build(ls, left, mid);
    build(rs, mid + 1, right);

    pushUp(root);
}

// 加法更新
void updateAdd(int root, int left, int right, int from, int to, int val) {
    
    // 两个区间无重合
    if (from > right || to < left) {
    
        return;
    }
    // 包含在[from, to]的区间才更新
    if (from <= left && to >= right) {
    
        segTree[root].val =
            (segTree[root].val + val * (right - left + 1)) % mod;
        segTree[root].lazyAdd = (segTree[root].lazyAdd + val) % mod;
        return;
    }

    pushDown(root, left, right);

    int mid = (right - left) / 2 + left;
    updateAdd(ls, left, mid, from, to, val);
    updateAdd(rs, mid + 1, right, from, to, val);

    pushUp(root);
}

// 乘法更新
void updateMul(int root, int left, int right, int from, int to, int val) {
    
    // 两个区间无重合
    if (from > right || to < left) {
    
        return;
    }
    // 包含在[from, to]的区间才更新
    if (from <= left && to >= right) {
    
        segTree[root].val = (segTree[root].val * val) % mod;
        segTree[root].lazyMul = (segTree[root].lazyMul * val) % mod;
        // 加法值也同步更新
        segTree[root].lazyAdd = (segTree[root].lazyAdd * val) % mod;
        return;
    }

    pushDown(root, left, right);

    int mid = (right - left) / 2 + left;
    updateMul(ls, left, mid, from, to, val);
    updateMul(rs, mid + 1, right, from, to, val);

    pushUp(root);
}

// 查询
int query(int root, int left, int right, int from, int to) {
    
    // 两个区间无重合
    if (from > right || to < left) {
    
        return 0;
    }
    // 完全包含
    if (from <= left && to >= right) {
    
        return segTree[root].val;
    }

    pushDown(root, left, right);

    int mid = (right - left) / 2 + left;
    return (query(ls, left, mid, from, to) +
            query(rs, mid + 1, right, from, to)) %
           mod;
}

signed main() {
    
    int n, m;
    cin >> n >> m >> mod;

    segTree.resize(n << 2);
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++) {
    
        cin >> arr[i];
    }

    build(1, 1, n);

    for (int i = 1, ask; i <= m; i++) {
    
        cin >> ask;
        int from, to, val;
        if (ask == 1) {
      // 乘法
            cin >> from >> to >> val;
            updateMul(1, 1, n, from, to, val);
        } else if (ask == 2) {
      // 加法
            cin >> from >> to >> val;
            updateAdd(1, 1, n, from, to, val);
        } else {
    
            cin >> from >> to;
            cout << query(1, 1, n, from, to) << endl;
        }
    }

    return 0;
}

区间计次区间求次数 (map 自动开点)

例题：力扣：731. 我的日程安排表 II
日程安排表123都是这个模板

构造目标：
区间操作次数累计，求操作最大次数
因为是操作次数，因此都1点1点累计的
也可以视为区间加值区间求最值
实现思路：
首先明确一点核心，这里的要求是操作次数而不是值的大小。
在一个区间中每个点所被作用的次数是一样的，单点代表的次数和区间的次数是一样的
因此是直接累计次数，并不是像加值一样还要乘上区间长度！
本题可以拓展一些思路和维度
区间的累计亦是一种覆盖
下面在pushDown()的两种写法的最终的效果是一样的
segTree[root<<1].val = segTree[root<<1].val + segTree[root].lazy;
segTree[root<<1|1].val += segTree[root].lazy;
第一种=是把左边的值全部覆盖
理解为先获得该子区间的最大值segTree[root<<1].val，再累计上segTree[root].lazy计算出一个新值
实际操作是覆盖到左边的变量上去，这是一种覆盖的思想
第二种是 +=是常规的加值操作
直接将lazy的值加到子区间中，是一种加值的思想(这里是计次数，每次只+1次)
动态开点(自动开点)
本题与之前常规的线段树有一定不同，那就是没有初始化n * 4的线段树组数，且没有build()操作
原因在于本题的区间范围n最大到达1e9的范围，常规数组直接会爆空间
因此我们必须动态的申请空间，需要多少申请多少，这里我们直接借助map 和 unordered_map的特性，可以做到自动开点
且这类题通常没有需要初始化的数值条件，因此也不需要build()
但是抛开动态开点这点，会发现update query pushDonw pushUp的编写方式和思路完全不受影响，可见动态开点不是这类题的根本难点

class MyCalendarTwo {
    
private:
    /// 动态开点没有build最好都初始化
    struct SegTreeNode {
    
        int val = 0;
        int lazy = 0;
    };

    // map 天然的能动态开点
    unordered_map<int, SegTreeNode> segTree;

    // 区间最值
    void pushUp(int root) {
    
        segTree[root].val = max(segTree[root<<1].val, segTree[root<<1|1].val);
    }
    
    // 区间累加
    // 累计型，val 和 lazy都要将状态累计
    void pushDown(int root) {
    
        if (segTree[root].lazy != 0) {
    
            segTree[root<<1].val = segTree[root<<1].val + segTree[root].lazy;
            segTree[root<<1|1].val += segTree[root].lazy;
            segTree[root<<1].lazy += segTree[root].lazy;
            segTree[root<<1|1].lazy += segTree[root].lazy;
            segTree[root].lazy = 0;
        }
    }

    void update(int root, int left, int right, int from, int to, int val) {
    
        if (to < left || from > right) {
    
            return ;
        }
        if (from <= left && right <= to) {
    
            segTree[root].val += val;
            segTree[root].lazy += val;
            return ;
        }
        
        pushDown(root);
        int mid = left + (right - left) / 2;
        update(root<<1, left, mid, from, to, val);
        update(root<<1|1, mid+1, right, from, to, val);
        pushUp(root);
    }

    int query(int root, int left, int right, int from, int to) {
    
        if (to < left || from > right) {
    
            return 0;
        }
        if (from <= left && right <= to) {
    
            return segTree[root].val;
        }
        
        pushDown(root);
        int mid = left + (right - left) / 2;
        return max(query(root<<1, left, mid, from, to), 
                query(root<<1|1, mid+1, right, from, to) );
    }

public:
    MyCalendarTwo() {
    }
    
    bool book(int start, int end) {
    
        end -= 1;
        /// [from, to]区间的最大值
        if (query(1, 0, 1e9, start, end) >= 2) {
    
            return false;
        }
        /// [from, to]区间累计+1
        update(1, 0, 1e9, start, end, 1);
        return true;
    }
};

/** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo* obj = new MyCalendarTwo(); * bool param_1 = obj->book(start,end); */

区间覆盖区间求最值 (map 自动开点)

例题：力扣：699. 掉落的方块

构造目标：
区间覆盖区间求最值
先获得原始区间的最值，在累计后覆盖回去
实现思路：
这就是典型的区间覆盖问题
当一个大的区间覆盖了新值，那么对应的左右子区间也是要这个值
因此在pushDown()中root.val 覆盖到 ls.val 和 rs.val 上
lazy也是直接由root覆盖到左右，但是这里的lazy其实只是做一个需要覆盖到子区间的标记而已，类似于true false
但是这里还有一种写法
就是在pushDown()中的左右子区间的val和lazy全部覆盖为root.lazy
这种表示其实是看怎么理解lazy的含义
全覆盖成root.lazy的话就是既把lazy作为需要覆盖的标记，又作为需要覆盖的值
若本题的覆盖为0怎么办，这个时候由于lazy背负多重含义
一定要明确出怎样才是pushDown()中if成立的条件
可见lazy代表太多含义又是可能并不会省力太多

class Solution {
    
#define ls (root << 1)
#define rs (root << 1 | 1)

private:
    struct SegTreeNode {
    
        int val = 0;
        int lazy = 0;
    };
    
    unordered_map<int, SegTreeNode> segTree;

    void pushUp(int root) {
    
        segTree[root].val = max(segTree[ls].val, segTree[rs].val);
    }

    void pushDown(int root) {
    
        if (segTree[root].lazy != 0) {
    
            segTree[ls].val = segTree[root].val;
            segTree[rs].val = segTree[root].val;
            segTree[ls].lazy = segTree[root].lazy;
            segTree[rs].lazy = segTree[root].lazy;
            segTree[root].lazy = 0;
        }
    }

    void update(int root, int left, int right, int from, int to, int val) {
    
        if (from > right || to < left) {
    
            return;
        }
        if (from <= left && right <= to) {
    
            segTree[root].val = val;
            segTree[root].lazy = val;
            return;
        }
        pushDown(root);
        int mid = left + (right - left) / 2;
        update(ls, left, mid, from, to, val);
        update(rs, mid + 1, right, from, to, val);
        pushUp(root);
    }

    int query(int root, int left, int right, int from, int to) {
    
        if (from > right || to < left) {
    
            return 0;
        }
        if (from <= left && right <= to) {
    
            return segTree[root].val;
        }

        pushDown(root);
        int mid = left + (right - left) / 2;
        return max(query(ls, left, mid, from, to), query(rs, mid + 1, right, from, to));
    }

public:
    const int n = 1e8;

    vector<int> fallingSquares(vector<vector<int>>& positions) {
    
        vector<int> ans(positions.size());

        for (int i = 0; i < positions.size(); i++) {
    
            int left = positions[i][0],
                right = positions[i][0] + positions[i][1] - 1,
                len = positions[i][1];

            int pre = query(1, 1, n, left, right);
            update(1, 1, n, left, right, len + pre);
            // ans[i] = segTree[1].val;
            ans[i] = query(1, 1, n, 1, n);
        }

        return ans;
    }
};

区间覆盖 true or false 区间计数 (动态开点指针)

例题：力扣：2276. 统计区间中的整数数目
本题数据量1e5用unordered_map自动开点超时

构造目标：
区间覆盖 true or false 区间计数
true 表示该区间可获得
false 表示该区间不可获得
实现思路：
本题的计数是每个点贡献1个单位
如果是一个连续的区间，那么可以利用区间长度来计算
然后若需要将该区间视为可取的话，可以设置为true
代码中由lazy = 1表示true
指针动态开点
很简单，就是在需要的时候开，那就是要在分左右子树的时候开点。
这里写在update query 或者 pushDown都行
本题操作次数是1e5 map的自动开点会超时，(前面的题1e4map可以过)
还有，这题写了析构居然也超！(力扣对C++太不友好了)
其实动态开点还有预估点数的做法，但我不怎么会估。。。

class CountIntervals {
    
private:
    struct SegTreeNode {
    
        int val = 0;
        int lazy = 0;
        SegTreeNode* ls = nullptr;
        SegTreeNode* rs = nullptr;
    };

    SegTreeNode* segTree = new SegTreeNode();

    // 累计数量
    void pushUp(SegTreeNode* root) {
    
        root->val = root->ls->val + root->rs->val;
    }

    void pushDown(SegTreeNode* root, int left, int right) {
    
        int mid = left + (right - left) / 2;
        int leftLen = mid - left + 1;
        int rightLen = right - mid;

        // 本题只有累计的状态，没有消除的状态
        // 因此这里的val 可乘可不乘lazy
        if (root->lazy != 0) {
    
            root->ls->val = leftLen * root->lazy;
            root->rs->val = rightLen * root->lazy;
            root->ls->lazy = root->lazy;
            root->rs->lazy = root->lazy;

            root->lazy = 0;
        }
    }

    void update(SegTreeNode* root, int left, int right, int from, int to, int val) {
    
        if (from > right || to < left) {
    
            return;
        }
        if (from <= left && right <= to) {
    
            root->val = val * (right - left + 1);
            root->lazy = val;
            return;
        }

        if (nullptr == root->ls) {
    
            root->ls = new SegTreeNode();
        }
        if (nullptr == root->rs) {
    
            root->rs = new SegTreeNode();
        }

        pushDown(root, left, right);
        int mid = left + (right - left) / 2;
        update(root->ls, left, mid, from, to, val);
        update(root->rs, mid + 1, right, from, to, val);
        pushUp(root);
    }

    int query(SegTreeNode* root, int left, int right, int from, int to) {
    
        if (from > right || to < left) {
    
            return 0;
        }
        if (from <= left && right <= to) {
    
            return root->val;
        }

        if (nullptr == root->ls) {
    
            root->ls = new SegTreeNode();
        }
        if (nullptr == root->rs) {
    
            root->rs = new SegTreeNode();
        }

        pushDown(root, left, right);
        int mid = left + (right - left) / 2;
        return query(root->ls, left, mid, from, to) +
               query(root->rs, mid + 1, right, from, to);
    }

public:
    const int n = 1e9;

    CountIntervals() {
    }

    // 析构超时
    // ~CountIntervals() {
    
    // function<void(SegTreeNode*)> deleteNode = [&](SegTreeNode* root) {
    
    // if (nullptr != root->ls) {
    
    // deleteNode(root->ls);
    // }
    // if (nullptr != root->rs) {
    
    // deleteNode(root->rs);
    // }
    // delete root;
    // };

    // deleteNode(segTree);
    // }

    void add(int left, int right) {
     
        update(segTree, 1, n, left, right, 1); 
    }

    int count() {
     
        return query(segTree, 1, n, 1, n); 
    }
};

/** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */

区间覆盖 true or false 区间求和 (树链剖分)

例题：杭电：Problem - 5221 Occupation

构造目标：
区间覆盖 true or false
区间为true的求和
初始全false，后续可改为true或者false
初始化每个点的值 (均不可获得)
操作1 x到y之间设为可获得
操作2 x到y之间设为不可获得
操作3 求x到y之间的和 (可获得的值)
实现思路：
树链剖分这里直接套模板即可
这里我们设定三种变量
val 目标的计算值
sum 该区间的和
lazy 状态改变标记
由于本题可由true -> false也可false -> true
因此可以引出第三种状态来进行区分，这里舍lazy = -1为不需要pushDown的状态 (关键)
如果有状态的变化，那就将 sum * lazy(true | false) 赋值到val上
关于要求的pushUp()很显然我们的目标是求区间的和，很自然的是将左右子树的val 的和赋值到root上
但是在build()并非如此，第一点在于初始状态全部为false那这个求和也没有意义
在这我们还要预处理出每个区间的和
因此这里的build需要一个预处理sum的pushUp
这就体现了线段树可能每部分写的模板相似，但是实际的操作作用和细节都不相同！

/** * 5221 Occupation * https://acm.hdu.edu.cn/showproblem.php?pid=5221 * 树链剖分 + 线段树 */
#include <bits/stdc++.h>
#define int long long
using namespace std;

#define ls (root << 1)
#define rs (root << 1 | 1)

/** *************************************************************************/
const int M = 10 + 100000;

vector<int> oldVal(M);
vector<int> newVal(M);
/** *************************************************************************/

static int n;
struct SegTreeNode {
    
    int val;
    int lazy;
    int sum;
};
vector<SegTreeNode> segTree(M << 2);

void pushUp(int root) {
     
    segTree[root].val = segTree[ls].val + segTree[rs].val; 
}

void pushDown(int root) {
    
    if (segTree[root].lazy != -1) {
    
        // 整个区间覆盖 以lazy来判断如何记录这个区间的sum
        segTree[ls].val = segTree[ls].sum * segTree[root].lazy;
        segTree[rs].val = segTree[rs].sum * segTree[root].lazy;
        // lazy传递下去
        segTree[ls].lazy = segTree[root].lazy;
        segTree[rs].lazy = segTree[root].lazy;

        segTree[root].lazy = -1;
    }
}

void build(int root, int left, int right) {
    
    segTree[root].val = segTree[root].sum = 0;
    // 0->1 1->0 不好区分则用三色标记
    segTree[root].lazy = -1;
    if (left == right) {
    
        segTree[root].sum = newVal[left];
        return;
    }
    int mid = left + (right - left) / 2;
    build(ls, left, mid);
    build(rs, mid + 1, right);
    // pushUp(root);
    // build 的初始只需要计算区间和即可
    segTree[root].sum = segTree[ls].sum + segTree[rs].sum;
}

void update(int root, int left, int right, int from, int to, int val) {
    
    if (from > right || to < left) {
    
        return;
    }
    // 整个区间覆盖 以val 来判断如何记录这个区间的sum
    // 而lazy只是为了把val记录下来罢了
    if (from <= left && right <= to) {
    
        segTree[root].val = segTree[root].sum * val;
        segTree[root].lazy = val;
        return;
    }
    pushDown(root);
    int mid = left + (right - left) / 2;
    update(ls, left, mid, from, to, val);
    update(rs, mid + 1, right, from, to, val);
    pushUp(root);
}

int query(int root, int left, int right, int from, int to) {
    
    if (from > right || to < left) {
    
        return 0;
    }
    if (from <= left && right <= to) {
    
        return segTree[root].val;
    }
    pushDown(root);
    int mid = left + (right - left) / 2;
    return query(ls, left, mid, from, to) + query(rs, mid + 1, right, from, to);
}
/** *************************************************************************/

// 树链剖分模板
vector<vector<int>> graph(M);
vector<int> father(M);
vector<int> deep(M);
vector<int> size(M);
vector<int> son(M);
vector<int> top(M);
vector<int> idx(M);
int cnt = 0;

void dfs1(int cur, int from) {
    
    deep[cur] = deep[from] + 1;  // 深度，从来向转化来
    father[cur] = from;          // 父节点，记录来向
    size[cur] = 1;               // 子树的节点数量
    son[cur] = 0;                // 重孩子 (先默认0表示无)
    for (int& to : graph[cur]) {
    
        if (to == from) {
      // 避免环
            continue;
        }
        dfs1(to, cur);                    // 处理子节点
        size[cur] += size[to];            // 节点数量叠加
        if (size[son[cur]] < size[to]) {
      // 松弛操作，更新重孩子
            son[cur] = to;
        }
    }
}

void dfs2(int cur, int grandfather) {
    
    top[cur] = grandfather;     // top记录祖先
    idx[cur] = ++cnt;           // 记录剖分id
    newVal[cnt] = oldVal[cur];  // 映射到新值
    if (son[cur] != 0) {
            // 优先dfs重儿子
        dfs2(son[cur], grandfather);
    }
    for (int& to : graph[cur]) {
    
        if (to == father[cur] || to == son[cur]) {
    
            continue;  // 不是cur的父节点，不是重孩子
        }
        dfs2(to, to);  // dfs轻孩子
    }
}
/** *************************************************************************/

void updatePath(int x, int y, int val) {
    
    while (top[x] != top[y]) {
    
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);
        }
        update(1, 1, n, idx[top[x]], idx[x], val);
        x = father[top[x]];
    }
    if (deep[x] < deep[y]) {
    
        swap(x, y);
    }
    update(1, 1, n, idx[y], idx[x], val);
}

void updateTree(int root, int val = true) {
    
    update(1, 1, n, idx[root], idx[root] + size[root] - 1, val);
}
/** *************************************************************************/

void solve() {
    
    scanf("%lld", &n);

    cnt = 0;
    for (int i = 1; i <= n; i++) {
    
        newVal[i] = father[i] = son[i] = top[i] = deep[i] = idx[i] = size[i] =
            0;
        graph[i].clear();
        scanf("%lld", &oldVal[i]);
    }
    // 建图
    for (int i = 1, u, v; i <= n - 1; i++) {
    
        scanf("%lld %lld", &u, &v);
        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
    }
    // 跑树链剖分
    dfs1(1, 0);
    dfs2(1, 1);
    // 建立线段树
    build(1, 1, n);

    int Q = 0;
    scanf("%lld", &Q);
    for (int i = 1, ask; i <= Q; i++) {
    
        scanf("%lld", &ask);
        int from, to, pos, subTree;
        if (ask == 1) {
    
            scanf("%lld %lld", &from, &to);
            updatePath(from, to, 1);
        } else if (ask == 2) {
    
            scanf("%lld", &pos);
            updatePath(pos, pos, 0);
        } else {
    
            scanf("%lld", &subTree);
            updateTree(subTree);
        }

        printf("%lld\n", query(1, 1, n, 1, n));
        // printf("%lld\n", segTree[1].val); // 因为是求整个区间，这么写等效
    }
}

signed main() {
    
    int T = 1;
    scanf("%lld", &T);
    while (T--) {
    
        solve();
    }

    return 0;
}

区间合并子序列 (LCIS 最长严格递增子序列)

例题：杭电：LCIS - 3308

个人认为本题是本文中最难的一题
构造目标：
求出目标区间内的最长递增子序列
可以动态修改某个点的值
实现思路：
区间合并这类题的要点在于如何求值pushUp()
区间类题一般具有三个变量
val 要求的目标值 代码中对应 SegTreeNode::val
lval 该区间左边前缀的状态 代码中对应 SegTreeNode::lmax
rval 该区间右边后缀的状态 代码中对应 SegTreeNode::rmax
在pushUp()中是借助左右子区间的值该更新root的值
首先是三个最起码
root.lmax 最起码是 ls.lmax 当前的前缀最起码是左子树的前缀值
root.rmax 最起码是 rs.rmax 当前的后缀最起码是右子树的后缀值
root.val 最起码是 max(ls.val, rs.val) 当前的目标值最起码是左右子树中最大的值
然后是考虑一个前提，三个能否
**前提：**左右子树的状态可连接 arr[mid] < arr[mid+1]
这个前提是根据题目要求而定的，本题是求最长严格递增子序列，那就是需要左子树的末端 < 右子树的首端
在满足前提的条件下，在对root的三个变量进行更新
关于三个能否也是需要依题而定，本题是求最长严格递增子序列，每个点的贡献是1，因此这也和区间长度有关
左子树的前缀是否饱和？
若左子树的前缀 == 左子树的长度
(当前的前缀继承自左子树的前缀)
当前的前缀累计上右子树的前缀
右子树的后缀是否饱和？
若右子树的后缀 == 右子树的长度
(当前的后缀继承自右子树的后缀)
当前的后缀累计上左子树的后缀
满足前提，则表示左子树的后缀可以连接右子树的前缀
将左右连接的状态和当前的值进行松弛操作
同理，在query()的时候也需要这么操作
注意这里的合并还要考虑递归空间的合法性才可以，区间不合规要提前return
在松弛root.val的时候也要保证ls和rs的区间合法性
因为ls和rs表示的是[left, right]的状态，而当前的目标是[from， to]
因此还要做两次min保证区间合法性

/** * 杭电 LCIS 严格递增 * https://acm.hdu.edu.cn/showproblem.php?pid=3308 * 单点修改，区间查询 * 区间合并 经典例题 */
#include <bits/stdc++.h>
using namespace std;
#define ls (root << 1)
#define rs (root << 1 | 1)

const int M = 10 + 100000;
// 结构体中维护的是下标root的LCIS的最大值
struct SegTreeNode {
    
    int val;         // 总区间最大值
    int lmax, rmax;  // 左右，前缀后缀最大值
};

SegTreeNode segTree[M << 2];
int arr[M];

// ls和rs能给root的贡献
void pushUp(int root, int left, int right) {
    
    // 左侧的前缀直接抄左边，右侧的后缀直接抄右边
    segTree[root].lmax = segTree[ls].lmax;
    segTree[root].rmax = segTree[rs].rmax;
    segTree[root].val = max(segTree[ls].val, segTree[rs].val);

    int mid = (right - left) / 2 + left;
    int leftLen = mid - left + 1;
    int rightLen = right - mid;
    if (arr[mid] < arr[mid + 1]) {
    
        // 左侧全覆盖，则可接上右侧的前缀
        if (segTree[root].lmax == leftLen) {
    
            segTree[root].lmax += segTree[rs].lmax;
        }
        // 右侧全覆盖，则可接上左侧的后缀
        if (segTree[root].rmax == rightLen) {
    
            segTree[root].rmax += segTree[ls].rmax;
        }
        // 和 左侧的后缀+右侧的前缀 比较
        segTree[root].val =
            max(segTree[root].val, segTree[ls].rmax + segTree[rs].lmax);
    }
}

void build(int root, int left, int right) {
    
    if (left == right) {
    
        // 初始均为1，单个点，长度为1的区间的LCIS为1
        segTree[root].val = segTree[root].lmax = segTree[root].rmax = 1;
        return;
    }

    int mid = (right - left) / 2 + left;
    build(ls, left, mid);
    build(rs, mid + 1, right);
    pushUp(root, left, right);
}

void update(int root, int left, int right, int from, int to, int val) {
    
    if (from > right || to < left) {
    
        return;
    }
    if (from <= left && right <= to) {
    
        // val已经在调用前使用，这里规范的写一下而已
        return;
    }

    int mid = (right - left) / 2 + left;
    update(ls, left, mid, from, to, val);
    update(rs, mid + 1, right, from, to, val);
    pushUp(root, left, right);
}

int query(int root, int left, int right, int from, int to) {
    
    if (from > right || to < left) {
    
        return 0;  // 这里返回1也可以，但逻辑不对
    }
    if (from <= left && right <= to) {
    
        return segTree[root].val;
    }

    int mid = (right - left) / 2 + left;
    int lmax = query(ls, left, mid, from, to);
    int rmax = query(rs, mid + 1, right, from, to);
    // 右侧压根没分到，只考虑左侧
    if (to < mid) {
    
        return lmax;
    }
    // 左侧压根没分到，只考虑右侧
    if (from > mid) {
    
        return rmax;
    }

    // 上面提前return了，现在左右都有贡献值
    int ans = max(lmax, rmax);
    if (arr[mid] < arr[mid + 1]) {
    
        // 左侧的后缀 和 右侧的前缀 合并
        // 保证区间在[from, to]内，做两次min
        ans = max(ans, min(mid - from + 1, segTree[ls].rmax) +
                           min(to - mid, segTree[rs].lmax));
    }

    return ans;
}

void solve() {
    
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
    
        cin >> arr[i];
    }

    build(1, 1, n);

    for (int i = 1, a, b; i <= m; i++) {
    
        char ch;
        cin >> ch >> a >> b;

        if (ch == 'U') {
    
            a += 1;      // 本题输入是[0, n-1]
            arr[a] = b;  // 直接在原序列上改
            // 还是要update() 目的是为了pushUp()
            update(1, 1, n, a, a, b);
        } else {
    
            a += 1, b += 1;
            cout << query(1, 1, n, a, b) << endl;
        }
    }
}

int main(void) {
    
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++) {
    
        solve();
    }
    return 0;
}

区间合并字串 (最大子序和)

例题：力扣：53. 最大子数组和

构造目标：
求出目标区间内的最大字串和
实现思路：
注意子串是连续的，子序列是可以不连续的
子串天然的必须连接，不想子序列一样需要有连接前提。(具体如何连接的思路见上一题)
因此可以直接将赋值和连接的松弛合并着写
注意本题需要预处理一个当前区间的sum和，着跟目标的val是两个作用的变量

class Solution {
    
#define ls (root << 1)
#define rs (root << 1 | 1)

private:
    struct SegTreeNode {
    
        // 最大子序和
        int val;
        // 该区间 左侧前缀子序和最大，右侧后缀子序和最大
        int lmax, rmax;
        // 区间内总和
        int sum;
    };

    vector<int> arr;
    vector<SegTreeNode> segTree;

    void pushUp(int root) {
    
        segTree[root].sum = segTree[ls].sum + segTree[rs].sum;
        segTree[root].lmax =
            max(segTree[ls].lmax, segTree[ls].sum + segTree[rs].lmax);
        segTree[root].rmax =
            max(segTree[rs].rmax, segTree[rs].sum + segTree[ls].rmax);
        segTree[root].val = max(max(segTree[ls].val, segTree[rs].val),
                                segTree[ls].rmax + segTree[rs].lmax);
    }

    void build(int root, int left, int right) {
    
        segTree[root].val = segTree[root].lmax = segTree[root].rmax =
            segTree[root].sum = 0;
        if (left == right) {
    
            segTree[root].val = segTree[root].lmax = segTree[root].rmax =
                segTree[root].sum = arr[left];
            return;
        }

        int mid = left + (right - left) / 2;
        build(ls, left, mid);
        build(rs, mid + 1, right);
        pushUp(root);
    }

public:
    int maxSubArray(vector<int>& nums) {
    
        int n = nums.size();
        this->segTree.resize(n << 2);
        this->arr.resize(n + 1);
        /// [1, n]
        for (int i = 1; i <= n; i++) {
    
            arr[i] = nums[i - 1];
        }

        build(1, 1, n);
        return segTree[1].val;
    }
};

区间深度

其实这根线段树没太大关系了
这里提一下已知区间长度，计算区间深度的方法

例题：牛客：D-和谐之树_“华为杯” 武汉大学21级新生程序设计竞赛

// 计算深度 len为区间长度
int getDeep(int len) {
    
    int deep = 1;
    while (len != 1) {
    
        len = (len + 1) >> 1;
        deep ++;
    }
    return deep;
}

query默认值问题区间求最值为例

例题：POJ：3264 – Balanced Lineup
力扣：239. 滑动窗口最大值
线段树天然能解决RMQ问题

构造目标：
求区间的最值
实现思路：
这里主要说明的是，我们做题时要时刻注意数据范围
比如我们求数值大小的时候，不能死板的将默认值设定为0
要根据题目需求和数据范围来编写
这也可能受我这个模板的影响，因为我是无脑递归的
在query()中如果在mid后分情况递归，一定程度上可以避免这种问题

/** * POJ Balanced Lineup * https://vjudge.csgrandeur.cn/problem/POJ-3264 * http://poj.org/problem?id=3264 */
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

const int M = 10 + 50000;
struct SegTreeNode {
    
    int maxx;
    int minn;
};

vector<SegTreeNode> segTree(M << 2);
vector<int> arr(M);

void pushUp(int root) {
    
    segTree[root].maxx =
        max(segTree[root << 1].maxx, segTree[root << 1 | 1].maxx);
    segTree[root].minn =
        min(segTree[root << 1].minn, segTree[root << 1 | 1].minn);
}

void build(int root, int left, int right) {
    
    if (left == right) {
    
        segTree[root].maxx = arr[left];
        segTree[root].minn = arr[left];
        return;
    }

    int mid = left + (right - left) / 2;
    build(root << 1, left, mid);
    build(root << 1 | 1, mid + 1, right);
    pushUp(root);
}

int queryMax(int root, int left, int right, int from, int to) {
    
    if (from > right || to < left) {
    
        return INT_MIN;
    }
    if (from <= left && right <= to) {
    
        return segTree[root].maxx;
    }

    int mid = left + (right - left) / 2;
    return max(queryMax(root << 1, left, mid, from, to),
               queryMax(root << 1 | 1, mid + 1, right, from, to));
}

int queryMin(int root, int left, int right, int from, int to) {
    
    if (from > right || to < left) {
    
        return INT_MAX;
    }
    if (from <= left && right <= to) {
    
        return segTree[root].minn;
    }

    int mid = left + (right - left) / 2;
    return min(queryMin(root << 1, left, mid, from, to),
               queryMin(root << 1 | 1, mid + 1, right, from, to));
}

int main() {
    
    int n, Q;
    scanf("%d %d", &n, &Q);

    for (int i = 1; i <= n; i++) {
    
        scanf("%d", &arr[i]);
    }

    build(1, 1, n);

    while (Q--) {
    
        int from, to;
        scanf("%d %d", &from, &to);
        printf("%d\n",
               queryMax(1, 1, n, from, to) - queryMin(1, 1, n, from, to));
    }

    return 0;
}