线段树 (Segment Tree)：区间分治与懒标记

树状数组把“单点加、区间求和”处理得很漂亮，配合差分还能做区间加。可如果题目接着要求整段翻转、一会儿乘一会儿加，或者动态查询区间最值，怎么办？

这次我们把区间一层层拆开，让每个节点负责一段。查询时找几段拼起来，修改时能整段处理就不再往下跑——这就是线段树的思路。

一、线段树核心定义与问题背景

在处理区间数据时，如果我们需要同时进行频繁的区间修改（如给区间内的每个数加上一个值）和频繁的区间查询（如求区间的和、区间最大值等），常规的方法往往难以兼顾两种操作的效率。如果直接用循环逐个修改节点，修改操作的复杂度将退化为 $O(N)$ ，遇到大规模数据时必定超时。

线段树（Segment Tree）则是解决这类复杂区间问题的全能数据结构。它将每一个子区间都表示为一个独立的树状节点，在 $O(\log N)$ 的时间复杂度内，高效处理动态的区间最值、区间求和等问题。

通俗理解： “金字塔式的层级承包商”。

想象一个庞大的基建工程，划分为 $1 \sim n$ 个标段：

最底层的员工（叶子节点）：每人只负责一个具体的单点标段。
中层主管（内部节点）：每个人负责把手下两个小团队负责的标段合并起来，汇总成一个大标段的数据（最大值、求和等）。
总经理（根节点）：掌控全局，负责整个 $1 \sim n$ 标段的汇总结果。

当总部想要查询或者修改某一个区间时，不需要逐个通知底层员工，只需要找到完全管辖这个区间的“中层主管”，让他直接给出汇总报告或签收修改指令即可。

线段树：查询区间的无重叠拆分

二、核心原理与深度推导 (Structure & Lazy-Tag)

1. 一个节点负责哪一段？

线段树是一棵严格的二叉树。对于代表区间 $[l, r]$ 的节点 $u$ ：

其左子节点代表前半段区间 $[l, mid]$ ，索引固定为 u << 1（即 $u \times 2$ ）。
其右子节点代表后半段区间 $[mid + 1, r]$ ，索引固定为 u << 1 | 1（即 $u \times 2 + 1$ ）。

线段树的区间二分与节点编号

数学空间的错位陷阱：

假设我们要为长度 $n = 5$ 的数组建线段树。

根节点为 $1$ ，管辖 $[1, 5]$ 。它的两部分是 $[1, 3]$ （索引 $2$ ）和 $[4, 5]$ （索引 $3$ ）。
看右边这个索引为 $3$ 的节点，它进一步分成 $[4, 4]$ （索引 $6$ ）和 $[5, 5]$ （索引 $7$ ）。
再看左边索引为 $2$ 的节点 $[1, 3]$ ，进一步分成 $[1, 2]$ （索引 $4$ ）和 $[3, 3]$ （索引 $5$ ）。
此时，索引为 $4$ 的节点 $[1, 2]$ 还要最后分裂一次，分成 $[1, 1]$ （索引 $8$ ）和 $[2, 2]$ （索引 $9$ ）。

原数组明明只有 $5$ 个元素，可是在二叉树的连续排布下，叶子节点的最高索引居然达到了 $9$ ！

节点编号不等于原数组下标。我们用 u*2 和 u*2+1 编号时，直接给 tr 开 4*N 就够用，先记住这个常用写法即可。

2. 状态向上传递 (`pushup`)

父亲的数据是由两个儿子拼凑出来的。

如果是求区间和：父亲的值 = 左儿子的值 + 右儿子的值。
如果是求区间最大值：父亲的值 = max(左儿子的值, 右儿子的值)。

这步操作叫 pushup。它是自底向上组装数据的核心，通常在递归回溯时触发。只有儿子是正确的，父亲通过 pushup 组装出来的总区间和（或最大值）才是正确的。

pushup：由两个孩子合并父区间

3. 懒惰标记 (Lazy Tag) 的推迟结算智慧

区间修改如果一路修改到最底层的叶子节点，复杂度会直接退化为 $O(N)$ ，线段树就失去了意义。

核心机制： 当修改指令下发，如果你当前走到的线段树节点 $u$ ，它的管辖范围 $[tr[u].l, tr[u].r]$ 被目标修改区间 $[l, r]$ 完全包裹时，修改立刻停止！

我们在 $u$ 节点打上一个标记：tr[u].lazy += v，同时把 $u$ 节点本身代表的区间和更新掉（加上 v * 区间长度），然后直接 return，绝对不往下走！此时， $u$ 下面的儿子和孙子们，还完全不知道自己被加了 $v$ ，这笔账先“欠着”。

4. 账目对齐：`pushdown` 的清算时机

既然账目欠着，那什么时候清算？

只有当接下来的操作（无论是新的修改还是查询），不得不进入 $u$ 的子树内部去获取更细致的信息时，如果还带着模糊的账目，数据就会出错。这时，我们必须调用 pushdown 赶紧把账目下传一层，分发给它的左右儿子。

通过这种“需要细账时再往下传”的做法，本讲这些区间操作都可以在 $O(\log N)$ 内完成。

5. 懒标记到底欠了谁的账？

拿 a=[1,2,3,4] 试一下。根节点管 [1,4]，原来的和是 10。

给整个 [1,4] 加 3：根节点的和立刻变成 $10+4\times3=22$ ，记下 lazy=3，先不动孩子。
此时问整个 [1,4]：直接报 22。根节点不是旧账，它已经更新好了。
接着问 [2,3]：这次要往下看，先把根的标记传给两个孩子。左半段的和变成 9，右半段变成 13；继续按需下传后，取出位置 2 的 5 和位置 3 的 6，答案是 11。

所以懒的是向下通知，不是当前节点不更新。下传时孩子的值和标记一起改，传完清掉父亲的标记，避免下次重复加。

Lazy Tag 下传前后：区间和与标记的变化

三、标准求解算法与五大函数模板

下面把一个节点的区间端点、统计值和懒标记放进同一个 struct，读代码时就能顺着节点查账。大写 N 是数组上限，小写 n 是本次输入的长度。

线段树的执行流程是一个经典的二分递归，其三大核心操作的动态轨迹如下：

build(1, 1, n)（筑基建树）：自上而下对半切开，分治建立左、右子树，递归到叶子节点填入初始值，最后回溯时自底向上调用 pushup 稳固大底座。
modify(1, l, r, v)（区间账目改动）：若被目标修改区间完全覆盖，打上 lazy 标记并更新当前值立刻返回。若部分重叠，必须先调用 pushdown 对齐下传账目，再左右分治，回溯时由 pushup 刷新父节点的值。
query(1, l, r)（区间账目查询）：若完全包裹直接返回正确的 tr[u].val。若部分包裹，同样必须先调用 pushdown 拨正账目，再分头去左右儿子里累加答案。

完整代码直接放在下面的 P3372 中，边看五个函数边对照刚才的例子，不再单独复制一遍模板。

四、洛谷实战真题演练 (由浅入深阶梯)

1. 💡 【实战例题 1：区间修改与区间查询基础篇】洛谷 P3372 【模板】线段树 1

题目大意：已知一个数列，你需要进行两种操作：1. 将区间 $[l, r]$ 内的每个数加上 $x$ 。2. 输出区间 $[l, r]$ 内每一个数的和。
思路引导：线段树最经典的常规基础应用。直接套用讲义标准求和模板，区间修改调用 modify(1, l, r, x)，区间查询调用 query(1, l, r)。
完整参考代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int a[N];

struct Node {
    int l, r, val, lazy;
} tr[N * 4];

inline void pushup(int u) {
    tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

inline void pushdown(int u) {
    if (tr[u].lazy) {
        int ls = u << 1, rs = u << 1 | 1, k = tr[u].lazy;
        tr[ls].lazy += k, tr[ls].val += k * (tr[ls].r - tr[ls].l + 1);
        tr[rs].lazy += k, tr[rs].val += k * (tr[rs].r - tr[rs].l + 1);
        tr[u].lazy = 0;
    }
}

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

void modify(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].lazy += v;
        tr[u].val += v * (tr[u].r - tr[u].l + 1);
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1;
    if (l <= mid) modify(ls, l, r, v);
    if (r > mid) modify(rs, l, r, v);
    pushup(u);
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].val;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1, ans = 0;
    if (l <= mid) ans += query(ls, l, r);
    if (r > mid) ans += query(rs, l, r);
    return ans;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, l, r, x; cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            modify(1, l, r, x);
        } else {
            cout << query(1, l, r) << "\n";
        }
    }
    return 0;
}

2. 💡 【实战例题 2：算子替换之区间极值篇】洛谷 P1531 I Hate It

题目大意：已知一组学生的成绩。需要两种操作：1. 改变单点 $i$ 的成绩为 $v$ （如果新成绩比原来低则不改）。2. 查询区间 $[l, r]$ 内的学生最高分。
思路引导：线段树非常擅长处理这类非和性信息。我们需要把模板里的“加法”算子彻底替换为“最大值”算子。请务必注意：不仅 pushup 和 modify 要改，query 函数也必须同步修改——将区间拼接时的累加 ans += 替换为 ans = max(ans, ...)，且初始最大值 ans 应当赋予一个极小值（本题成绩为正数，用 -1 即可）。由于本题是单点更新，不需要懒标记，我们可以直接去掉所有的 pushdown 提高效率。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int a[N];

struct Node {
    int l, r, val; // 仅维护单点，不需要懒标记
} tr[N * 4];

inline void pushup(int u) {
    tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val); // 加法变极值
}

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

void modify(int u, int i, int v) {
    if (tr[u].l == tr[u].r) {
        tr[u].val = max(tr[u].val, v); // 如果新成绩更高则更新单点
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1;
    if (i <= mid) modify(ls, i, v);
    else modify(rs, i, v);
    pushup(u);
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].val; // 完美包裹直接返回当前区间的最大值
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1, ans = -1; // 初始化为极小值
    if (l <= mid) ans = max(ans, query(ls, l, r)); // 左右子区间取最大值，绝不能写成 +=
    if (r > mid) ans = max(ans, query(rs, l, r));
    return ans;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        char op; int l, r; cin >> op >> l >> r;
        if (op == 'U') {
            modify(1, l, r);
        } else {
            cout << query(1, l, r) << "\n";
        }
    }
    return 0;
}

3. 💡 【实战例题 3：算子替换之区间位运算篇】洛谷 P2574 XOR的艺术

题目大意：给你一个 01 序列。需要两种操作：1. 将区间 $[l, r]$ 内的所有数进行异或 1 翻转（0变1，1变0）。2. 查询区间 $[l, r]$ 内 1 的个数。
思路引导：区间取反问题。当一个长度为 $len$ 的区间被翻转时，其中 1 的个数会变为：len - 当前1的个数。懒标记 lazy 只需要记录当前区间被翻转了奇数次（1）还是偶数次（0），每次下传时，子节点的 lazy ^= 1 即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int a[N];

struct Node {
    int l, r, val, lazy;
} tr[N * 4];

inline void pushup(int u) {
    tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

inline void pushdown(int u) {
    if (tr[u].lazy) {
        int ls = u << 1, rs = u << 1 | 1;
        tr[ls].lazy ^= 1, tr[ls].val = (tr[ls].r - tr[ls].l + 1) - tr[ls].val; // 长度减去原1的个数
        tr[rs].lazy ^= 1, tr[rs].val = (tr[rs].r - tr[rs].l + 1) - tr[rs].val;
        tr[u].lazy = 0;
    }
}

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

void modify(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].lazy ^= 1;
        tr[u].val = (tr[u].r - tr[u].l + 1) - tr[u].val;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1;
    if (l <= mid) modify(ls, l, r);
    if (r > mid) modify(rs, l, r);
    pushup(u);
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].val;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1, ans = 0;
    if (l <= mid) ans += query(ls, l, r);
    if (r > mid) ans += query(rs, l, r);
    return ans;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m;
    string s; cin >> s;
    for (int i = 1; i <= n; i++) a[i] = s[i - 1] - '0';
    build(1, 1, n);
    while (m--) {
        int op, l, r; cin >> op >> l >> r;
        if (op == 0) {
            modify(1, l, r);
        } else {
            cout << query(1, l, r) << "\n";
        }
    }
    return 0;
}

4. 💡 【实战例题 4：高阶多标记联动篇】洛谷 P3373 【模板】线段树 2

题目大意：已知一个数列，你需要进行三种操作：1. 区间 $[l, r]$ 所有数乘以 $x$ 。2. 区间 $[l, r]$ 所有数加上 $x$ 。3. 查询区间 $[l, r]$ 的和对 $p$ 取模的值。
思路引导：线段树的终极模板，需要在一个节点中维护两个懒标记（一个加法标记 add，一个乘法标记 mul）。

核心难点在于双标记下传时的优先级。我们把单个数的待办操作统一记成 $x\times mul+add$ 。再乘以 m，展开就是 $x\times(mul\times m)+(add\times m)$ 。

记住： 当乘法操作来临时，不仅乘法标记要乘，原有的加法标记也必须跟着乘以 $m$ 。

比如先加 3、再乘 2，得到的是 $(x+3)\times2=2x+6$ ，所以标记应该是 mul=2, add=6，不是 mul=2, add=3。先乘后加和先加后乘，真的不是一回事。

下传时，孩子已有的 mul、add 代表较早的操作，父亲传来的是后来的操作。于是孩子的加法标记要先乘父亲的 mul，再加父亲的 add。区间和也别漏了长度：加法贡献是 add*len。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5; 
int a[N], p;

struct Node {
    int l, r;
    int val, add, mul; // 包含乘法和加法双标记
} tr[N * 4];

inline void pushup(int u) {
    tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val) % p;
}

inline void pushdown(int u) {
    int ls = u << 1, rs = u << 1 | 1;
    // 核心下传：先计算乘法标记对子节点值和标记的影响，再结算加法标记
    tr[ls].val = (tr[ls].val * tr[u].mul + tr[u].add * (tr[ls].r - tr[ls].l + 1)) % p;
    tr[ls].mul = (tr[ls].mul * tr[u].mul) % p;
    tr[ls].add = (tr[ls].add * tr[u].mul + tr[u].add) % p; // 关键：子节点原本的加法标记也得先乘以父节点的乘法标记

    tr[rs].val = (tr[rs].val * tr[u].mul + tr[u].add * (tr[rs].r - tr[rs].l + 1)) % p;
    tr[rs].mul = (tr[rs].mul * tr[u].mul) % p;
    tr[rs].add = (tr[rs].add * tr[u].mul + tr[u].add) % p;

    tr[u].mul = 1, tr[u].add = 0; // 父节点标记重置
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0, 1}; // 乘法标记初始必须为 1
    if (l == r) {
        tr[u].val = a[l] % p;
        return;
    }
    int mid = (l + r) >> 1, ls = u << 1, rs = u << 1 | 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
}

void modify_mul(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].val = (tr[u].val * v) % p;
        tr[u].mul = (tr[u].mul * v) % p;
        tr[u].add = (tr[u].add * v) % p; // 区间乘法来临时，当前节点的加法账目也扩大 v 倍
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1;
    if (l <= mid) modify_mul(ls, l, r, v);
    if (r > mid) modify_mul(rs, l, r, v);
    pushup(u);
}

void modify_add(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].add = (tr[u].add + v) % p;
        tr[u].val = (tr[u].val + v * (tr[u].r - tr[u].l + 1)) % p;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1;
    if (l <= mid) modify_add(ls, l, r, v);
    if (r > mid) modify_add(rs, l, r, v);
    pushup(u);
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].val % p;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1, ans = 0;
    if (l <= mid) ans = (ans + query(ls, l, r)) % p;
    if (r > mid) ans = (ans + query(rs, l, r)) % p;
    return ans;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, l, r, x; cin >> op >> l >> r;
        if (op == 1) {
            cin >> x, modify_mul(1, l, r, x); // 乘法操作
        } else if (op == 2) {
            cin >> x, modify_add(1, l, r, x); // 加法操作
        } else {
            cout << query(1, l, r) << "\n";   // 询问操作
        }
    }
    return 0;
}

五、选学：高阶标记联动——区间赋值与区间加

问题场景：不仅需要给一段区间全体加上 $x$ ，还可能会收到指令，将一段区间全体强制变成 $v$ 。

状态含义：一个节点上需要两个标记：add（加法标记）和 set（赋值标记）。为了区分“赋值为 0”和“还没发生过赋值”，我们需要额外加一个 has_set 布尔值。

关键推导：操作的先后顺序决定了标记的去留。

如果先“加”再“赋值”，原先的加法就灰飞烟灭了。因此，每次发生区间赋值时，必须无情地清空节点上原有的加法标记。
如果先“赋值”再“加”，这相当于在新的基准线上累加。因此，遇到加法操作时，不需要动赋值标记，只需把数值累加到 add 上即可。

手算演示：假设区间 [1, 2] 初始为 0。

区间加 3：add = 3, has_set = false。区间和 $6$ 。
区间赋值为 5：set = 5, has_set = true。注意：add 必须清零！区间和变为 $5 \times 2 = 10$ 。
区间加 2：add 变为 2。此时节点状态是 set = 5, add = 2。这代表着“先被强制变成了 5，然后又加了 2”。区间和加上 $2 \times 2 = 4$ ，变为 $14$ 。

实现要点 (pushdown)：下传时，先下传赋值标记，再下传加法标记。父亲的赋值标记一旦落到儿子身上，同样必须清空儿子原本的 add 标记。

inline void pushdown(int u) {
    int ls = u << 1, rs = u << 1 | 1;
    // 1. 优先结算霸道的赋值标记
    if (tr[u].has_set) {
        tr[ls].has_set = tr[rs].has_set = true;
        tr[ls].set = tr[rs].set = tr[u].set;
        tr[ls].add = tr[rs].add = 0; // 核心：赋值抹杀原有一切加法
        tr[ls].val = tr[u].set * (tr[ls].r - tr[ls].l + 1);
        tr[rs].val = tr[u].set * (tr[rs].r - tr[rs].l + 1);
        tr[u].has_set = false;
    }
    // 2. 再结算平民的加法标记
    if (tr[u].add) {
        tr[ls].add += tr[u].add;
        tr[rs].add += tr[u].add;
        tr[ls].val += tr[u].add * (tr[ls].r - tr[ls].l + 1);
        tr[rs].val += tr[u].add * (tr[rs].r - tr[rs].l + 1);
        tr[u].add = 0;
    }
}

六、选学：算子重构——区间最大子段和

问题场景：给定序列，支持单点修改数值，并频繁查询某段区间 $[L, R]$ 内的最大连续子段和。

状态含义：由于最大子段和不满足简单的“左边+右边”叠加律，我们需要把区间彻底剖开，在 pushup 时维护四个信息：

sum：区间总和。
lmax：必须紧贴左端点的最大子段和。
rmax：必须紧贴右端点的最大子段和。
mmax：区间内真正的最大子段和（位置任意）。

关键推导：如何由左儿子 ls 和右儿子 rs 拼出父亲 u？

sum：就是左右 sum 之和。
lmax：要么完全没有跨越左儿子（就是 ls.lmax）；要么跨越了整个左儿子，吃掉了右儿子的一部分前缀（ls.sum + rs.lmax）。两者取大。
rmax：同理，取 rs.rmax 和 rs.sum + ls.rmax 中的较大值。
mmax：有三种可能。完全在左儿子里（ls.mmax），完全在右儿子里（rs.mmax），或者刚好跨越了左右儿子的边界（左儿子的 rmax + 右儿子的 lmax）。三者取最大。

手算演示：左半段 [2, -1]：sum=1, lmax=2, rmax=1, mmax=2 右半段 [3, -2]：sum=1, lmax=3, rmax=1, mmax=3 合并它们：跨越中界的和 = 左 rmax (1) + 右 lmax (3) = 4。父亲的 mmax = max(2, 3, 4) = 4。对应的正是子段 [2, -1, 3]。

完整参考代码 (对应题目：洛谷 P4513 小白逛公园)：

/*
独立输入输出及范围：
第一行两个整数 N, M (1 <= N, M <= 500000)，表示数列长度和操作次数。
第二行 N 个整数，表示初始数列。
接下来 M 行，每行三个整数 op, x, y。
若 op=1，查询区间 [x, y] 的最大子段和（可能 x > y，需交换）。
若 op=2，将第 x 个数修改为 y。

样例输入：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 2 3
样例输出：
2
-1
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5;
int a[N];

struct Node {
    int l, r;
    int sum, lmax, rmax, mmax;
} tr[N * 4];

inline void pushup(int u) {
    int ls = u << 1, rs = u << 1 | 1;
    tr[u].sum = tr[ls].sum + tr[rs].sum;
    // 关键推导的四个公式代码化
    tr[u].lmax = max(tr[ls].lmax, tr[ls].sum + tr[rs].lmax);
    tr[u].rmax = max(tr[rs].rmax, tr[rs].sum + tr[ls].rmax);
    tr[u].mmax = max({tr[ls].mmax, tr[rs].mmax, tr[ls].rmax + tr[rs].lmax});
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].sum = tr[u].lmax = tr[u].rmax = tr[u].mmax = a[l];
        return;
    }
    int mid = (l + r) >> 1, ls = u << 1, rs = u << 1 | 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}

void modify(int u, int p, int v) {
    if (tr[u].l == tr[u].r) {
        tr[u].sum = tr[u].lmax = tr[u].rmax = tr[u].mmax = v;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1;
    if (p <= mid) modify(ls, p, v);
    else modify(rs, p, v);
    pushup(u);
}

// 核心难点：查询时不仅要返回值，还要返回由多个相邻区间拼凑出的虚拟 Node
Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    int mid = (tr[u].l + tr[u].r) >> 1, ls = u << 1, rs = u << 1 | 1;
    
    if (r <= mid) return query(ls, l, r);
    if (l > mid) return query(rs, l, r);
    
    // 如果查询区间跨越了中点，必须把左右结果作为虚拟节点再 pushup 一次
    Node left = query(ls, l, r);
    Node right = query(rs, l, r);
    Node res;
    res.sum = left.sum + right.sum;
    res.lmax = max(left.lmax, left.sum + right.lmax);
    res.rmax = max(right.rmax, right.sum + left.rmax);
    res.mmax = max({left.mmax, right.mmax, left.rmax + right.lmax});
    return res;
}

void solve() {
    int n, m;
    if (!(cin >> n >> m)) return;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) {
            if (x > y) swap(x, y); // 坑点：查询区间不保证正序
            cout << query(1, x, y).mmax << "\n";
        } else {
            modify(1, x, y);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

七、选学：结构利用——线段树上二分

问题场景：在一个动态变化的数组中，快速找到区间 $[L, R]$ 内第一个大于等于 $k$ 的数的位置。

传统思路：在外面套一层二分答案（ $O(\log N)$ ），每次二分去线段树里查询区间最大值（ $O(\log N)$ ），总复杂度 $O(\log^2 N)$ 。

降维打击：既然线段树的节点已经存了它管辖区间的最大值 val（即本区间内的最大元素），我们为何不直接在线段树上“看路牌”往下走？

如果当前区间的最大值都小于 $k$ ，说明这个区间绝对没有满足条件的数，直接掉头。
既然要找“第一个”，我们就优先钻进左儿子。
只有当左儿子找不着（返回 -1）时，才去右儿子找。每次最多只会探入一到两条有效路径，时间复杂度直降为 $O(\log N)$ 。

手算演示：在 [3, 1, 6, 4] 中找第一个 $\ge 5$ 的数（全区间查询）。根节点 [1, 4] 记录最大值是 6，且 $6 \ge 5$ ，允许进入。左儿子 [1, 2] 最大值是 3。因为 $3 < 5$ ，左半边没戏，直接掉头（返回 -1）。转头去右儿子 [3, 4]，最大值是 6，进入。右儿子的左儿子 [3, 3] 最大值是 6，符合条件且是叶子，直接返回位置 3。

实现代码片段：

这里的 tr[u].val 存的是区间最大值，不是前面求和模板里的区间和。片段按没有懒标记的版本写；如果维护了懒标记，就要在进入孩子前先调用 pushdown(u)，让孩子的最大值也是最新的。

// 在线段树上寻找区间 [L, R] 内第一个 >= k 的位置
int query_first(int u, int L, int R, int k) {
    // 1. 若当前区间不在查询范围内，或者本区间的最大值都小于 k，肯定找不到
    if (tr[u].l > R || tr[u].r < L || tr[u].val < k) return -1;
    
    // 2. 若到达叶子节点，说明这就是要找的目标
    if (tr[u].l == tr[u].r) return tr[u].l;
    
    // 3. 优先查左半边（为了找"第一个"）
    int res = query_first(u << 1, L, R, k);
    
    // 4. 如果左半边没找到，再去右半边找
    if (res == -1) {
        res = query_first(u << 1 | 1, L, R, k);
    }
    
    return res;
}

八、模板怎么改，才不容易漏？

题目	节点存什么	修改整段后怎么变	懒标记怎么合并
P3372 区间加	区间和	`val += x*len`	加上 x
P1531 单点提高	区间最大值	修改叶子，再向上取 max	不需要
P2574 区间翻转	1 的个数	`val = len-val`	异或 1
P3373 区间乘加	区间和	`val = valmul+addlen`	按操作先后组合

写变式时不要只改 modify：pushup、query 的合并方式也要一起看。懒标记是否好用，关键是能不能直接更新这一段的汇总值，以及两次操作能不能合成一个标记。

本讲建树 $O(n)$ ，修改和查询 $O(\log n)$ ，空间 $O(n)$ 。下一节暂时离开区间，去处理另一类常见问题：哪些点属于同一伙？

线段树