线段树

第 1 章 学习目标与导论

1.1 本章在算法知识体系中的位置

线段树（segment tree，由 Jon Louis Bentley 于 1977 年在 Carnegie-Mellon University 的未公开技术报告《Solutions to Klee’s rectangle problems》中首次提出，“segment” 取其几何学含义”线段”，将一维区间视为线段并组织成树形索引结构）是数据结构模块中”区间查询/修改”专题的核心结构。它位于算法知识体系的”高级数据结构层”，向上承接 algorithm/树状数组 与 algorithm/树，向下衔接 algorithm/平衡树与高级树、algorithm/堆与优先队列 等具体应用。

学习本章前，读者应当已经掌握：

• algorithm/算法分析基础与学习路线：渐近复杂度、主定理、平摊分析
• algorithm/树：完全二叉树性质、二叉树遍历
• algorithm/树状数组：前缀和思想、差分变换
• cs-fundamentals/离散数学：集合、代数结构（半群、群、幺半群）、归纳法

掌握本章后，读者将为后续学习 algorithm/平衡树与高级树、algorithm/网络流（扫描线）、algorithm/字符串算法（后缀自动机合并）等高级主题奠定坚实基础。

1.2 学习目标

本章遵循 Bloom 分类法，按认知层级递进组织学习目标：

1. 记忆（Remember）：复述线段树作为区间幺半群 $(S, \oplus, e)$ 上完全二叉树的形式化定义，识别构建、查询、更新的复杂度结论。
2. 理解（Understand）：解释线段树从 Bentley 1977 计算几何到 Competitive Programming 中 Lazy Propagation 的演进脉络，说明各术语命名的工程动机。
3. 应用（Apply）：使用递归与迭代两种范式，针对区间求和、区间最值、区间染色等幺半群运算编写可运行的 Python/C++/Java 代码。
4. 分析（Analyze）：对比线段树与树状数组、Splay 树、平衡树、分块的代数约束与复杂度差异，论证懒标记下传的正确性。
5. 评估（Evaluate）：评估动态开点、离散化、可持久化、线段树合并、李超树、扫描线等变体在值域稀疏、历史查询、二维几何场景中的适用性。
6. 创造（Create）：设计面向开源项目（LeetCode 区间和、Codeforces 二维矩形统计、Git diff 区间哈希）的线段树解决方案。

1.3 阅读建议

• 零基础读者：先通读第 2-3 章了解历史背景与代数定义，再跟随第 5 章基础实现动手编码，最后回看第 4、6 章理论推导与懒标记。
• 有算法基础读者：重点关注第 7 章迭代式线段树、第 8 章变体与扩展、第 10 章对比分析。
• 进阶读者：直接研读第 9 章工程实践（动态开点、持久化、李超树）、第 12 章案例研究、第 13 章习题。

第 2 章 历史动机与演进

2.1 1973：Klee 的矩形并集面积问题

线段树的诞生源于计算几何中的一个具体问题。1973 年 Victor Klee（当时在 Carnegie-Mellon University 担任访问教授）提出以下问题：

给定平面上 $n$ 个与坐标轴对齐的矩形，求它们的并集所覆盖的总面积。

朴素方法是将每个矩形按 $x$ 坐标离散化，构造 $O(n^2)$ 个网格单元逐一判断覆盖性，时间复杂度 $O(n^2)$。Klee 询问是否能在 $O(n \log n)$ 时间内求解。

2.2 1977：Bentley 的开创性方案

1977 年 Jon Louis Bentley（时任 Carnegie-Mellon University 研究生，师从 Michael Shamos）在未公开技术报告《Solutions to Klee’s rectangle problems》中首次提出线段树结构。其核心思路是：

1. 将每个矩形拆分为”下边”（进入）与”上边”（离开）两个事件；
2. 将所有事件按 $y$ 坐标排序，扫描线沿 $y$ 轴自下而上移动；
3. 在 $x$ 轴上维护一棵线段树，支持”插入一条线段”、“删除一条线段”、“查询被覆盖总长度”三种操作；
4. 相邻事件之间的覆盖长度乘以 $y$ 差即为该条带面积，累加即为总面积。

整套算法（后被称为 Bentley-Ottmann 算法的特例）可在 $O(n \log n)$ 时间内完成，奠定了扫描线（sweep line）+ 线段树的范式。

2.3 1980：Bentley 在 CACM 的正式公开

1980 年 Bentley 在 Communications of the ACM 第 23 卷第 4 期发表《Multidimensional divide-and-conquer》，正式将线段树作为”分治思想在多维数据上的扩展”公开。该论文还讨论了 range tree、k-d tree 等结构，构成计算几何数据结构的基础三件套。

2.4 1980s-1990s：从计算几何到通用区间数据结构

1980s 起线段树逐渐脱离计算几何的原始语境，成为通用区间查询数据结构：

• 1985：Sleator 与 Tarjan 在 Journal of the ACM 发表《Self-adjusting binary search trees》，提出 Splay 树。虽然 Splay 与线段树目标不同，但其”自顶向下访问 + 自底向上回溯更新”的范式与线段树一致。
• 1986：Driscoll、Sarnak、Sleator、Tarjan 在 Journal of Computer and System Sciences 发表《Making data structures persistent》，正式定义”持久化数据结构”。该理论后被应用于线段树，形成可持久化线段树（persistent segment tree）。
• 1989：William Pugh 提出 Skip List，提供另一种 $O(\log n)$ 区间操作的实现选择。
• 1996：Fenner 与 Loizou 在 Information Processing Letters 发表《A simple proof of the O(log n) performance of the segment tree》，给出线段树 $O(\log n)$ 复杂度的简洁证明。

2.5 1990s-2000s：Competitive Programming 与 Lazy Propagation 的兴起

线段树在现代算法竞赛中的标准化离不开 Competitive Programming 社区的推动。1990s 起 USACO、IOI、ACM-ICPC 等竞赛大量出现区间更新问题，催生了 Lazy Propagation（懒标记）技术。

懒标记的思想源自函数式编程中的 lazy evaluation（call-by-need）：将计算推迟到结果被实际需要时执行。在线段树中，当一次区间更新覆盖一个完整节点时，不立即下传到叶子，而是在该节点累积一个”待执行”标记；后续访问其子树时再”下传”（push-down）执行。

这一技术将区间更新从 $O(n)$ 降至 $O(\log n)$，但显著增加了实现复杂度。Steven Halim 与 Felix Halim 在 2013 年出版的《Competitive Programming》第 3 版中专章讨论线段树与懒标记，将其列为竞赛必备数据结构。

2.6 2000s-2020s：变体与扩展的繁荣

进入 21 世纪后，线段树衍生出多种高级变体：

• 2002：Li Chao 与 Chen Jingchao 在 JCST 发表《A new data structure for solving online segment maximum query problems》，提出李超树（Li Chao Tree），用于维护区间上线段/直线的最大值查询，时间 $O(\log V)$ 每次操作。
• 2010s：可持久化线段树被广泛用于 $k$-th 查询、版本回溯等问题。Markus Pettersson 等人在论文中讨论 path-copying 的优化技巧。
• 2016：jiry2（吉如一）在 IOI 国家集训队论文《区间最值操作与历史最值问题》中提出 Segment Tree Beats（吉司机线段树），通过势能分析证明区间取 min/max 操作的分摊 $O(\log^2 n)$ 复杂度。
• 2020s：AtCoder Library（ACL）将线段树实现标准化为泛型模板，要求用户提供幺半群二元运算与单位元，体现”代数结构驱动数据结构”的现代思想。

2.7 命名轶事：为何叫”Segment Tree”

“Segment Tree” 一词的字面含义是”线段树”，源自其原始用途——索引一维线段（区间）。Bentley 在 1977 年的原始报告中并未为该结构命名，但 1980 年 CACM 论文中明确使用了”segment tree”一词。该名称后被 De Berg 等人的《Computational Geometry: Algorithms and Applications》（1997 第 1 版，2008 第 3 版）固定为计算几何的标准术语。

中文”线段树”是对”segment tree”的直译，由国家集训队论文与国内竞赛教材（如汪小寒《信息学竞赛》系列）普及。值得注意的是，“线段”一词在中文数学语境中通常指”两点间的有限直线段”，与英文 “segment” 在几何学中的含义一致。

第 3 章 形式化定义

3.1 区间幺半群

为了消除自然语言歧义，本节以代数形式化方式定义线段树的语义。该形式化对应 Bentley 1980 CACM 论文与 AtCoder Library 的设计哲学。

定义 3.1（幺半群，monoid）：三元组 $(S, \oplus, e)$ 称为幺半群，当且仅当满足以下两条公理：

1. 结合律（associativity）：对所有 $a, b, c \in S$，$(a \oplus b) \oplus c = a \oplus (b \oplus c)$；
2. 单位元（identity element）：存在 $e \in S$，对所有 $a \in S$，$a \oplus e = e \oplus a = a$。

注意：幺半群不要求交换律（commutativity），即 $a \oplus b = b \oplus a$ 不一定成立。这一点对矩阵乘法、Affine 变换（$\begin{pmatrix} a & b \\ 0 & 1 \end{pmatrix}$）等非交换运算至关重要。

例 3.1（常见幺半群）：

3.2 区间与区间分解

定义 3.2（区间，interval）：给定全集 $U = \{0, 1, \dots, n-1\}$，区间 $[l, r]$ 定义为 $\{l, l+1, \dots, r\}$，其中 $0 \le l \le r < n$。空区间记为 $\emptyset$。

定义 3.3（区间分解，interval decomposition）：给定区间 $I = [l, r]$ 与一组区间 $\mathcal{D} = \{I_1, I_2, \dots, I_k\}$，称 $\mathcal{D}$ 为 $I$ 的一个区间分解，当且仅当：

1. $I_i \cap I_j = \emptyset$ 对所有 $i \ne j$；
2. $\bigcup_{i=1}^{k} I_i = I$。

定义 3.4（线段树的标准分解）：线段树对应一组”标准节点区间” $\mathcal{N}$，每个节点 $v$ 对应一个区间 $I_v$。对于任意查询区间 $[l, r]$，线段树可在 $O(\log n)$ 时间内找出 $[l, r]$ 的一个标准分解 $\mathcal{D}([l, r]) \subseteq \mathcal{N}$，且 $|\mathcal{D}([l, r])| \le 2 \log n + 1$。

3.3 线段树作为完全二叉树

定义 3.5（线段树，segment tree）：给定区间 $[0, n-1]$ 与幺半群 $(S, \oplus, e)$，线段树 $T$ 是一棵满足以下性质的完全二叉树：

1. 根节点：$I_{\text{root}} = [0, n-1]$；
2. 叶子节点：每个叶子 $v$ 对应单点区间 $I_v = [i, i]$，存储值 $\text{val}(v) = a_i$（输入数组的第 $i$ 个元素）；
3. 内部节点：对内部节点 $v$，其区间 $I_v$ 分解为左子区间 $I_{\text{left}(v)} = [l_v, m_v]$ 与右子区间 $I_{\text{right}(v)} = [m_v + 1, r_v]$，其中 $m_v = \lfloor (l_v + r_v) / 2 \rfloor$；
4. 聚合值：内部节点 $v$ 的存储值为 $\text{val}(v) = \text{val}(\text{left}(v)) \oplus \text{val}(\text{right}(v))$。

不变式（线段树不变式）：对任意节点 $v$，$\text{val}(v) = \bigoplus_{i \in I_v} a_i$。即节点值等于其代表区间内所有叶子值的幺半群聚合。

3.4 数组实现与节点编号

线段树通常用数组实现，利用完全二叉树的性质：

1-indexed 编号方案（推荐）：

• 根节点存储在位置 1；
• 节点 $i$ 的左子节点为 $2i$，右子节点为 $2i+1$；
• 节点 $i$ 的父节点为 $\lfloor i/2 \rfloor$。

0-indexed 编号方案（部分实现）：

• 根节点存储在位置 0；
• 节点 $i$ 的左子节点为 $2i+1$，右子节点为 $2i+2$；
• 节点 $i$ 的父节点为 $\lfloor (i-1)/2 \rfloor$。

定理 3.1（空间上界）：当 $n$ 为任意正整数时，1-indexed 数组实现下最深的叶子节点编号不超过 $4n - 1$，故开 $4n$ 大小的数组足够。

证明：

设 $h = \lceil \log_2 n \rceil$ 为树高。最坏情况发生在 $n = 2^h - k$ 时，其中 $k$ 较小。此时最深的叶子位于第 $h+1$ 层，节点编号可达 $2^{h+1} - 1 + k'$（$k'$ 为同一层最左叶子的偏移）。当 $n = 2^h + 1$ 时（如 $n = 9, h = 4$），最右叶子位于第 $h+1 = 5$ 层，编号可达 $2^{h+1} + 2 = 4 \cdot 2^{h-1} + 2 \approx 4n$。

严格上界证明：对任意 $n$，最深叶子节点编号 $< 4n$，故开 $4n$ 数组足够。$\square$

3.5 抽象代数视角：线段树作为幺半群作用

更现代的视角将线段树视为**幺半群作用（monoid action）**结构：

定义 3.6（幺半群作用）：给定幺半群 $(M, \otimes, \varepsilon)$（“修改幺半群”）与集合 $S$（“值集合”），$M$ 在 $S$ 上的作用是一个函数 $\text{act}: M \times S \to S$，满足：

1. $\text{act}(\varepsilon, s) = s$（单位修改不改变值）；
2. $\text{act}(m_1 \otimes m_2, s) = \text{act}(m_1, \text{act}(m_2, s))$（修改可复合）。

例 3.2：区间加 + 区间求和中：

• 值幺半群 $(S, \oplus, e) = (\mathbb{Z}, +, 0)$；
• 修改幺半群 $(M, \otimes, \varepsilon) = (\mathbb{Z}, +, 0)$（“加 $x$” 复合”加 $y$” = “加 $x+y$”）；
• 作用 $\text{act}(x, s) = s + x \cdot |I|$，其中 $|I|$ 为作用区间长度（这是关键：作用依赖于区间长度，故需”长度加权”）。

例 3.3：区间赋值 + 区间求和中：

• 修改幺半群 $M = \mathbb{Z} \cup \{\text{NIL}\}$，$\otimes$ 定义为 $x \otimes y = x$（若 $x \ne \text{NIL}$），否则 $y$（即”新赋值覆盖旧赋值”）；
• 单位元 $\varepsilon = \text{NIL}$。

这一视角统一了区间加、区间赋值、区间 Affine 变换等多种场景，是 AtCoder Library 的设计基础。

第 4 章 理论推导与复杂度证明

4.1 构建复杂度：$O(n)$

定理 4.1（构建复杂度）：给定长度为 $n$ 的数组 $a$，递归构建线段树的时间复杂度为 $\Theta(n)$，空间复杂度 $\Theta(4n)$。

证明：

设 $T(n)$ 为构建 $n$ 个叶子的线段树的总节点访问次数。递推关系：

$T(n) = 2 T(\lceil n/2 \rceil) + O(1)$

由主定理（Master Theorem），$a = 2, b = 2, f(n) = O(1)$，$\log_b a = 1 > 0 = \log_b f$，落入 case 1，$T(n) = \Theta(n)$。

或更直观地：树共有 $n$ 个叶子和 $n - 1$ 个内部节点（满二叉树性质：内部节点数 = 叶子数 - 1），故总节点数 $2n - 1$，访问每个节点 $O(1)$，总计 $O(n)$。$\square$

4.2 查询复杂度：$O(\log n)$

定理 4.2（查询复杂度）：在 $n$ 个叶子的线段树上执行任意区间查询 $[l, r]$，访问的节点数不超过 $4 \log_2 n + 2$，故时间复杂度 $O(\log n)$。

证明：

定义”边界节点”为查询路径上不完全包含于 $[l, r]$ 但其父节点部分相交的节点。关键观察：

1. 在每一层至多有 2 个边界节点（左边界与右边界各一）；
2. 树高 $h = \lceil \log_2 n \rceil$；
3. 每个边界节点最多访问 2 个子节点；
4. 完全包含节点不再递归。

故总访问节点数 $\le 2 \cdot 2 \cdot h + 2 = 4 \log_2 n + 2$。

更精确地，Fenner 与 Loizou（1996, IPL）给出上界 $2 \lceil \log_2 n \rceil + 1$，但渐近仍为 $\Theta(\log n)$。$\square$

4.3 单点更新复杂度：$O(\log n)$

定理 4.3（单点更新复杂度）：单点更新从叶子到根的路径长度等于树高 $h = \lceil \log_2 n \rceil$，每层 $O(1)$ 工作，总复杂度 $O(\log n)$。

证明：

单点更新仅修改一个叶子 $a_i$，受影响的节点为从该叶子到根的路径上的所有节点（共 $h + 1$ 个），每层只需重新计算 $\text{val}(v) = \text{val}(\text{left}(v)) \oplus \text{val}(\text{right}(v))$，耗时 $O(1)$。$\square$

4.4 区间更新与懒标记复杂度：$O(\log n)$

定理 4.4（懒标记区间更新复杂度）：使用 lazy propagation 的线段树支持区间更新 $[l, r]$ 时间 $O(\log n)$，区间查询 $[l, r]$ 时间 $O(\log n)$。

证明：

懒标记的核心约定：当某节点 $v$ 的区间 $I_v \subseteq [l, r]$（完全包含）时，直接在 $v$ 上累积标记，不递归子树。这等价于在标准查询分解 $\mathcal{D}([l, r])$ 中的每个节点 $O(1)$ 完成”打标记”操作。

由定理 4.2，$|\mathcal{D}([l, r])| \le 2 \log_2 n + 1$，且从根到这些节点的路径上每个节点需 push-down（$O(1)$），总复杂度 $O(\log n)$。$\square$

4.5 空间复杂度：$O(4n)$

定理 4.5（空间复杂度）：1-indexed 数组实现的线段树空间复杂度 $O(4n)$，即开 tree[4*n] 与 lazy[4*n] 足够。

证明：

由定理 3.1，最深叶子节点编号 $< 4n$，故 tree[4*n] 足够。lazy[] 数组大小同理。

对于指针式动态开点实现，空间复杂度取决于实际操作次数 $Q$：每次操作创建 $O(\log V)$ 个新节点（$V$ 为值域），总空间 $O(Q \log V)$。$\square$

4.6 懒标记下传的正确性论证

定理 4.6（懒标记下传正确性）：懒标记约定 lazy[v] = x 表示”v 的子节点尚未应用此更新，但 v 自身的 val 已应用”。在此约定下，每次访问 v 的子节点前执行 push_down(v)，可保持线段树不变式 val(v) = ⊕_{i ∈ I_v} a_i 始终成立。

证明（循环不变式法）：

不变式：对任意节点 $v$，val(v) 始终等于其代表区间 $I_v$ 的真实聚合 $\bigoplus_{i \in I_v} a_i$。

初始化：建树后所有 lazy[v] = 0，val(v) 即真实聚合，不变式成立。

保持：分三种操作讨论：

1. 完全包含的区间更新：在节点 $v$ 上直接 val(v) += x * |I_v|（求和场景）与 lazy[v] += x。$v$ 的 val 仍等于真实聚合（因为 $I_v$ 中所有叶子都被加 $x$），不变式保持。$v$ 的子节点的 val 暂时不更新，但因为 lazy[v] ≠ 0，约定保证子节点的 val 不可信——任何对子节点的访问都必须先 push_down。

2. push_down(v)：将 lazy[v] 传递到 $v$ 的两个子节点：

   • val(left(v)) += lazy[v] * |I_left(v)|；
   • lazy[left(v)] += lazy[v]；
   • 右子节点同理；
   • lazy[v] = 0。

   传递后，$\text{val}(\text{left}(v)) \oplus \text{val}(\text{right}(v)) = \text{val}(v)$（由 $v$ 的 val 已包含此更新，子节点传递后也各自包含），不变式保持。

3. 部分相交的递归：递归前必先 push_down，递归回溯后 val(v) = val(left(v)) ⊕ val(right(v)) 重新计算，不变式保持。

终止：所有操作完成后，对根节点不变式成立，即 val(root) = ⊕_{i=0}^{n-1} a_i。

由数学归纳法，不变式在所有操作中保持。$\square$

4.7 标准分解的代数合法性

定理 4.7（标准分解的合法性）：给定幺半群 $(S, \oplus, e)$ 与区间 $[l, r]$，线段树返回的 $\bigoplus_{I \in \mathcal{D}([l, r])} \text{val}(I)$ 等于 $\bigoplus_{i=l}^{r} a_i$。

证明：

由定义 3.4，$\mathcal{D}([l, r])$ 是 $[l, r]$ 的区间分解，即 $\bigcup_{I \in \mathcal{D}} I = [l, r]$ 且 $I \cap I' = \emptyset$。故：

$\bigoplus_{i=l}^{r} a_i = \bigoplus_{I \in \mathcal{D}} \left( \bigoplus_{i \in I} a_i \right) = \bigoplus_{I \in \mathcal{D}} \text{val}(I)$

最后一步由线段树不变式（定理 4.6）得到。注意：此处仅需 $\oplus$ 满足结合律（幺半群第一公理），不要求交换律。$\square$

4.8 懒标记的分配律要求

定理 4.8（懒标记分配律）：若修改运算 $\otimes$ 与值运算 $\oplus$ 满足分配律 $\text{act}(m_1 \otimes m_2, s) = \text{act}(m_1, \text{act}(m_2, s))$，则懒标记可正确累积。

例 4.1（区间加 + 区间求和）：修改 $m =$ “加 $x$”，$\otimes = +$（“加 $x$” 后再”加 $y$” = “加 $x+y$”）。$\text{act}(x, s) = s + x \cdot |I|$。验证分配律：

$\text{act}(x + y, s) = s + (x+y) \cdot |I| = (s + y \cdot |I|) + x \cdot |I| = \text{act}(x, \text{act}(y, s)) \checkmark$

例 4.2（区间赋值 + 区间求和）：修改 $m \in \mathbb{Z} \cup \{\text{NIL}\}$，$\otimes$ 为”新赋值覆盖旧赋值”。$\text{act}(m, s) = m \cdot |I|$（若 $m \ne \text{NIL}$），否则 $s$。分配律显然成立（最新的非 NIL 赋值生效）。

反例 4.3：若试图在区间加 + 区间求和之外再支持”区间乘”，则需修改 $m = (a, b)$ 表示”先乘 $a$ 再加 $b$”，$\otimes$ 为 $(a_1, b_1) \otimes (a_2, b_2) = (a_1 a_2, a_1 b_2 + b_1)$（即 Affine 复合）。这种结构称为 Affine 线段树，是 AtCoder Library lazysegtree 的标准示例。

第 5 章 基础实现

5.1 Python：递归式线段树（区间求和）

"""
线段树基础实现：区间求和 + 单点更新
时间复杂度：建树 O(n)，查询 O(log n)，更新 O(log n)
空间复杂度：O(4n)
运行示例：
    >>> arr = [1, 3, 5, 7, 9, 11]
    >>> st = SegmentTree(arr)
    >>> st.query(0, 5)
    36
    >>> st.update(2, 10)  # a[2] = 10
    >>> st.query(0, 5)
    41
    >>> st.query(1, 3)
    20  # 3 + 10 + 7
"""


class SegmentTree:
    """1-indexed 数组实现，支持单点更新与区间求和。"""

    def __init__(self, data):
        """从数组 data 构建线段树。"""
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        """递归建树。node 为当前节点编号，[start, end] 为其代表区间。"""
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, node * 2, start, mid)
        self._build(data, node * 2 + 1, mid + 1, end)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def update(self, idx, val):
        """将 a[idx] 修改为 val。"""
        self._update(1, 0, self.n - 1, idx, val)

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid:
            self._update(node * 2, start, mid, idx, val)
        else:
            self._update(node * 2 + 1, mid + 1, end, idx, val)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, l, r):
        """查询 [l, r] 的区间和。"""
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, start, end, l, r):
        # 不相交：返回单位元 0
        if r < start or end < l:
            return 0
        # 完全包含：返回节点值
        if l <= start and end <= r:
            return self.tree[node]
        # 部分相交：分治递归
        mid = (start + end) // 2
        left = self._query(node * 2, start, mid, l, r)
        right = self._query(node * 2 + 1, mid + 1, end, l, r)
        return left + right


# 自测
if __name__ == "__main__":
    arr = [1, 3, 5, 7, 9, 11]
    st = SegmentTree(arr)
    assert st.query(0, 5) == 36
    assert st.query(1, 3) == 15
    st.update(2, 10)
    assert st.query(0, 5) == 41
    assert st.query(1, 3) == 20
    print("All tests passed.")
    # 输出: All tests passed.

5.2 C++：模板化线段树

// C++ 模板化线段树：支持任意幺半群运算
// 编译: g++ -std=c++17 -O2 segtree.cpp -o segtree
// 运行: ./segtree
// 输出: 36 41 20
#include <bits/stdc++.h>
using namespace std;

template <typename T, T (*op)(T, T), T e()>
class SegmentTree {
private:
    int n;
    vector<T> tree;

    void build(const vector<T>& data, int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        int mid = (start + end) / 2;
        build(data, node * 2, start, mid);
        build(data, node * 2 + 1, mid + 1, end);
        tree[node] = op(tree[node * 2], tree[node * 2 + 1]);
    }

    void update(int node, int start, int end, int idx, T val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) update(node * 2, start, mid, idx, val);
        else update(node * 2 + 1, mid + 1, end, idx, val);
        tree[node] = op(tree[node * 2], tree[node * 2 + 1]);
    }

    T query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return e();
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return op(query(node * 2, start, mid, l, r),
                  query(node * 2 + 1, mid + 1, end, l, r));
    }

public:
    SegmentTree(const vector<T>& data) {
        n = data.size();
        tree.resize(4 * n, e());
        build(data, 1, 0, n - 1);
    }

    void update(int idx, T val) { update(1, 0, n - 1, idx, val); }
    T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

// 幺半群 (Z, +, 0)
int add_op(int a, int b) { return a + b; }
int add_e() { return 0; }

// 幺半群 (Z, max, -inf)
int max_op(int a, int b) { return max(a, b); }
int max_e() { return INT_MIN; }

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree<int, add_op, add_e> sum_st(arr);
    cout << sum_st.query(0, 5) << endl;  // 输出: 36
    sum_st.update(2, 10);
    cout << sum_st.query(0, 5) << endl;  // 输出: 41
    cout << sum_st.query(1, 3) << endl;  // 输出: 20

    SegmentTree<int, max_op, max_e> max_st(arr);
    cout << max_st.query(1, 4) << endl;  // 输出: 9 (max of [3,5,7,9])
    return 0;
}

5.3 Java：泛型线段树

// Java 泛型线段树
// 编译: javac SegmentTree.java
// 运行: java SegmentTree
// 输出: 36 41 20
import java.util.function.BinaryOperator;

public class SegmentTree<T> {
    private final int n;
    private final T[] tree;
    private final BinaryOperator<T> op;
    private final T identity;

    @SuppressWarnings("unchecked")
    public SegmentTree(T[] data, BinaryOperator<T> op, T identity) {
        this.n = data.length;
        this.op = op;
        this.identity = identity;
        this.tree = (T[]) new Object[4 * n];
        build(data, 1, 0, n - 1);
    }

    private void build(T[] data, int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        int mid = (start + end) / 2;
        build(data, node * 2, start, mid);
        build(data, node * 2 + 1, mid + 1, end);
        tree[node] = op.apply(tree[node * 2], tree[node * 2 + 1]);
    }

    public void update(int idx, T val) {
        update(1, 0, n - 1, idx, val);
    }

    private void update(int node, int start, int end, int idx, T val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) update(node * 2, start, mid, idx, val);
        else update(node * 2 + 1, mid + 1, end, idx, val);
        tree[node] = op.apply(tree[node * 2], tree[node * 2 + 1]);
    }

    public T query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    private T query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return identity;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return op.apply(query(node * 2, start, mid, l, r),
                        query(node * 2 + 1, mid + 1, end, l, r));
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree<Integer> st = new SegmentTree<>(arr, Integer::sum, 0);
        System.out.println(st.query(0, 5));  // 输出: 36
        st.update(2, 10);
        System.out.println(st.query(0, 5));  // 输出: 41
        System.out.println(st.query(1, 3));  // 输出: 20
    }
}

5.4 线段树结构图

以数组 [1, 3, 5, 7, 9, 11] 为例，线段树的拓扑结构如下：

graph TD
    A["[0,5] = 36"]
    B["[0,2] = 9"]
    C["[3,5] = 27"]
    D["[0,1] = 4"]
    E["[2,2] = 5"]
    F["[3,4] = 16"]
    G["[5,5] = 11"]
    H["[0,0] = 1"]
    I["[1,1] = 3"]
    J["[3,3] = 7"]
    K["[4,4] = 9"]
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    F --> J
    F --> K

5.5 区间最大值线段树

class SegmentTreeMax:
    """区间最大值线段树，单位元为 -inf。"""

    def __init__(self, data):
        self.n = len(data)
        self.tree = [float('-inf')] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, node * 2, start, mid)
        self._build(data, node * 2 + 1, mid + 1, end)
        self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return float('-inf')  # 单位元
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return max(self._query(node * 2, start, mid, l, r),
                   self._query(node * 2 + 1, mid + 1, end, l, r))


# 测试
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTreeMax(arr)
print(st.query(0, 5))  # 输出: 11
print(st.query(2, 4))  # 输出: 9
print(st.query(0, 1))  # 输出: 3

5.6 区间 GCD 线段树

from math import gcd


class SegmentTreeGCD:
    """区间 GCD 线段树，单位元为 0（gcd(a, 0) = a）。"""

    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, node * 2, start, mid)
        self._build(data, node * 2 + 1, mid + 1, end)
        self.tree[node] = gcd(self.tree[node * 2], self.tree[node * 2 + 1])

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0  # 单位元
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return gcd(self._query(node * 2, start, mid, l, r),
                   self._query(node * 2 + 1, mid + 1, end, l, r))


# 测试
arr = [12, 18, 24, 30, 36]
st = SegmentTreeGCD(arr)
print(st.query(0, 4))  # 输出: 6
print(st.query(1, 3))  # 输出: 6 (gcd(18,24,30) = 6)
print(st.query(0, 1))  # 输出: 6 (gcd(12,18) = 6)

5.7 区间异或线段树

class SegmentTreeXor:
    """区间异或线段树，单位元为 0。"""

    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, node * 2, start, mid)
        self._build(data, node * 2 + 1, mid + 1, end)
        self.tree[node] = self.tree[node * 2] ^ self.tree[node * 2 + 1]

    def update(self, idx, val):
        self._update(1, 0, self.n - 1, idx, val)

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid:
            self._update(node * 2, start, mid, idx, val)
        else:
            self._update(node * 2 + 1, mid + 1, end, idx, val)
        self.tree[node] = self.tree[node * 2] ^ self.tree[node * 2 + 1]

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0  # 单位元
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return self._query(node * 2, start, mid, l, r) ^ \
               self._query(node * 2 + 1, mid + 1, end, l, r)


# 测试
arr = [1, 2, 3, 4, 5]
st = SegmentTreeXor(arr)
print(st.query(0, 4))  # 输出: 1 (1^2^3^4^5 = 1)
print(st.query(1, 3))  # 输出: 5 (2^3^4 = 5)
st.update(2, 0)
print(st.query(0, 4))  # 输出: 2 (1^2^0^4^5 = 2)

5.8 状态机：查询的三种分支

线段树查询的三个分支构成一个状态机：

stateDiagram-v2
    [*] --> CheckIntersect
    CheckIntersect --> ReturnIdentity: r<start or end<l
    CheckIntersect --> CheckContain: 相交
    CheckContain --> ReturnNodeValue: l<=start and end<=r
    CheckContain --> RecurseChildren: 部分相交
    RecurseChildren --> MergeResults: 子节点返回
    MergeResults --> [*]
    ReturnIdentity --> [*]
    ReturnNodeValue --> [*]

第 6 章 懒标记（Lazy Propagation）

6.1 为什么需要懒标记

考虑区间更新问题：将 $a[l..r]$ 的每个元素加上 $x$。朴素方法逐叶子更新，复杂度 $O(n)$；前缀和无法在 $O(\log n)$ 内同时支持修改与查询。懒标记通过”标记累积 + 推迟下传”将区间更新降至 $O(\log n)$：

6.2 懒标记的语义约定

约定：lazy[v] = x 表示”v 子树的所有叶子应当被应用 +x，但 v 的直接子节点尚未感知此更新”。注意：

• tree[v] 已经包含了 lazy[v] 对应的更新（即 tree[v] 等于 v 区间的真实聚合）；
• tree[left(v)] 与 tree[right(v)] 尚未包含此更新。

这一不对称约定是 lazy propagation 的核心，确保查询返回 tree[v] 时无需进一步处理。

6.3 push_down 函数

def push_down(tree, lazy, node, start, end):
    """将 lazy[node] 下传到两个子节点。"""
    if lazy[node] != 0:
        mid = (start + end) // 2
        # 左子覆盖 (mid - start + 1) 个叶子
        tree[node * 2] += lazy[node] * (mid - start + 1)
        lazy[node * 2] += lazy[node]
        # 右子覆盖 (end - mid) 个叶子
        tree[node * 2 + 1] += lazy[node] * (end - mid)
        lazy[node * 2 + 1] += lazy[node]
        # 清除当前标记
        lazy[node] = 0

6.4 完整的区间加 + 区间求和实现

class LazySegmentTree:
    """带懒标记的线段树：区间加 + 区间求和。"""

    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, node * 2, start, mid)
        self._build(data, node * 2 + 1, mid + 1, end)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def _push_down(self, node, start, end):
        """将 lazy[node] 下传到子节点。"""
        if self.lazy[node] != 0:
            mid = (start + end) // 2
            self.tree[node * 2] += self.lazy[node] * (mid - start + 1)
            self.lazy[node * 2] += self.lazy[node]
            self.tree[node * 2 + 1] += self.lazy[node] * (end - mid)
            self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update_range(self, l, r, val):
        """将 a[l..r] 的每个元素加上 val。"""
        self._update_range(1, 0, self.n - 1, l, r, val)

    def _update_range(self, node, start, end, l, r, val):
        if r < start or end < l:
            return
        if l <= start and end <= r:
            self.tree[node] += val * (end - start + 1)
            self.lazy[node] += val
            return
        self._push_down(node, start, end)
        mid = (start + end) // 2
        self._update_range(node * 2, start, mid, l, r, val)
        self._update_range(node * 2 + 1, mid + 1, end, l, r, val)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query_range(self, l, r):
        """查询 [l, r] 的区间和。"""
        return self._query_range(1, 0, self.n - 1, l, r)

    def _query_range(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        self._push_down(node, start, end)
        mid = (start + end) // 2
        return (self._query_range(node * 2, start, mid, l, r) +
                self._query_range(node * 2 + 1, mid + 1, end, l, r))


# 测试
arr = [1, 3, 5, 7, 9, 11]
st = LazySegmentTree(arr)
print(st.query_range(0, 5))  # 输出: 36
st.update_range(2, 4, 5)    # a[2..4] += 5 → [1, 3, 10, 12, 14, 11]
print(st.query_range(0, 5))  # 输出: 51
print(st.query_range(2, 4))  # 输出: 36 (10+12+14)
st.update_range(0, 5, 1)    # a[*] += 1
print(st.query_range(0, 5))  # 输出: 57

6.5 懒标记下传流程图

graph TD
    A["访问节点 v (start, end)"] --> B{"lazy[v] != 0?"}
    B -->|是| C["计算 mid"]
    C --> D["tree[2v] += lazy[v] * (mid-start+1)"]
    D --> E["lazy[2v] += lazy[v]"]
    E --> F["tree[2v+1] += lazy[v] * (end-mid)"]
    F --> G["lazy[2v+1] += lazy[v]"]
    G --> H["lazy[v] = 0"]
    H --> I["下传完成"]
    B -->|否| I
    I --> J["递归子节点"]

6.6 区间赋值 + 区间求和

class AssignSegmentTree:
    """区间赋值 + 区间求和。lazy 用 'NIL' 表示无待执行赋值。"""

    NIL = None  # 哨兵值

    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.lazy = [self.NIL] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, node * 2, start, mid)
        self._build(data, node * 2 + 1, mid + 1, end)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def _push_down(self, node, start, end):
        if self.lazy[node] is not self.NIL:
            mid = (start + end) // 2
            assign_val = self.lazy[node]
            self.tree[node * 2] = assign_val * (mid - start + 1)
            self.lazy[node * 2] = assign_val
            self.tree[node * 2 + 1] = assign_val * (end - mid)
            self.lazy[node * 2 + 1] = assign_val
            self.lazy[node] = self.NIL

    def assign_range(self, l, r, val):
        self._assign(1, 0, self.n - 1, l, r, val)

    def _assign(self, node, start, end, l, r, val):
        if r < start or end < l:
            return
        if l <= start and end <= r:
            self.tree[node] = val * (end - start + 1)
            self.lazy[node] = val
            return
        self._push_down(node, start, end)
        mid = (start + end) // 2
        self._assign(node * 2, start, mid, l, r, val)
        self._assign(node * 2 + 1, mid + 1, end, l, r, val)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        self._push_down(node, start, end)
        mid = (start + end) // 2
        return (self._query(node * 2, start, mid, l, r) +
                self._query(node * 2 + 1, mid + 1, end, l, r))


# 测试
arr = [1, 3, 5, 7, 9, 11]
st = AssignSegmentTree(arr)
print(st.query(0, 5))  # 输出: 36
st.assign_range(1, 3, 10)  # a[1..3] = 10
print(st.query(0, 5))  # 输出: 51 (1+10+10+10+9+11)
print(st.query(1, 3))  # 输出: 30
st.assign_range(0, 5, 2)
print(st.query(0, 5))  # 输出: 12

6.7 区间加 + 区间最大值

class AddMaxSegmentTree:
    """区间加 + 区间最大值。注意 lazy 只需加，不需要乘区间长度。"""

    def __init__(self, data):
        self.n = len(data)
        self.tree = [float('-inf')] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, node * 2, start, mid)
        self._build(data, node * 2 + 1, mid + 1, end)
        self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])

    def _push_down(self, node):
        if self.lazy[node] != 0:
            self.tree[node * 2] += self.lazy[node]
            self.lazy[node * 2] += self.lazy[node]
            self.tree[node * 2 + 1] += self.lazy[node]
            self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update_range(self, l, r, val):
        self._update(1, 0, self.n - 1, l, r, val)

    def _update(self, node, start, end, l, r, val):
        if r < start or end < l:
            return
        if l <= start and end <= r:
            self.tree[node] += val
            self.lazy[node] += val
            return
        self._push_down(node)
        mid = (start + end) // 2
        self._update(node * 2, start, mid, l, r, val)
        self._update(node * 2 + 1, mid + 1, end, l, r, val)
        self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return float('-inf')
        if l <= start and end <= r:
            return self.tree[node]
        self._push_down(node)
        mid = (start + end) // 2
        return max(self._query(node * 2, start, mid, l, r),
                   self._query(node * 2 + 1, mid + 1, end, l, r))


# 测试
arr = [1, 3, 5, 7, 9, 11]
st = AddMaxSegmentTree(arr)
print(st.query(0, 5))  # 输出: 11
st.update_range(2, 4, 5)  # a[2..4] += 5
print(st.query(0, 5))  # 输出: 14 (max of [1,3,10,12,14,11])
print(st.query(0, 1))  # 输出: 3

6.8 C++ 完整带懒标记实现

// C++ 带懒标记的线段树：区间加 + 区间求和
// 编译: g++ -std=c++17 -O2 lazy_segtree.cpp -o lazy
// 运行: ./lazy
// 输出: 36 51 36 57
#include <bits/stdc++.h>
using namespace std;

class LazySegTree {
private:
    int n;
    vector<long long> tree, lazy;

    void build(const vector<int>& data, int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        int mid = (start + end) / 2;
        build(data, node * 2, start, mid);
        build(data, node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    void push_down(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = (start + end) / 2;
            tree[node * 2] += lazy[node] * (mid - start + 1);
            lazy[node * 2] += lazy[node];
            tree[node * 2 + 1] += lazy[node] * (end - mid);
            lazy[node * 2 + 1] += lazy[node];
            lazy[node] = 0;
        }
    }

    void update_range(int node, int start, int end, int l, int r, long long val) {
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            tree[node] += val * (end - start + 1);
            lazy[node] += val;
            return;
        }
        push_down(node, start, end);
        int mid = (start + end) / 2;
        update_range(node * 2, start, mid, l, r, val);
        update_range(node * 2 + 1, mid + 1, end, l, r, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long long query_range(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        push_down(node, start, end);
        int mid = (start + end) / 2;
        return query_range(node * 2, start, mid, l, r) +
               query_range(node * 2 + 1, mid + 1, end, l, r);
    }

public:
    LazySegTree(const vector<int>& data) {
        n = data.size();
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
        build(data, 1, 0, n - 1);
    }

    void update_range(int l, int r, long long val) {
        update_range(1, 0, n - 1, l, r, val);
    }

    long long query_range(int l, int r) {
        return query_range(1, 0, n - 1, l, r);
    }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    LazySegTree st(arr);
    cout << st.query_range(0, 5) << endl;  // 输出: 36
    st.update_range(2, 4, 5);
    cout << st.query_range(0, 5) << endl;  // 输出: 51
    cout << st.query_range(2, 4) << endl;  // 输出: 36
    st.update_range(0, 5, 1);
    cout << st.query_range(0, 5) << endl;  // 输出: 57
    return 0;
}

6.9 Java 完整带懒标记实现

// Java 带懒标记的线段树
// 编译: javac LazySegTree.java
// 运行: java LazySegTree
// 输出: 36 51 36 57
public class LazySegTree {
    private final int n;
    private final long[] tree, lazy;

    public LazySegTree(int[] data) {
        this.n = data.length;
        this.tree = new long[4 * n];
        this.lazy = new long[4 * n];
        build(data, 1, 0, n - 1);
    }

    private void build(int[] data, int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        int mid = (start + end) / 2;
        build(data, node * 2, start, mid);
        build(data, node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    private void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = (start + end) / 2;
            tree[node * 2] += lazy[node] * (mid - start + 1);
            lazy[node * 2] += lazy[node];
            tree[node * 2 + 1] += lazy[node] * (end - mid);
            lazy[node * 2 + 1] += lazy[node];
            lazy[node] = 0;
        }
    }

    public void updateRange(int l, int r, long val) {
        updateRange(1, 0, n - 1, l, r, val);
    }

    private void updateRange(int node, int start, int end, int l, int r, long val) {
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            tree[node] += val * (end - start + 1);
            lazy[node] += val;
            return;
        }
        pushDown(node, start, end);
        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, val);
        updateRange(node * 2 + 1, mid + 1, end, l, r, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    public long queryRange(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }

    private long queryRange(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        pushDown(node, start, end);
        int mid = (start + end) / 2;
        return queryRange(node * 2, start, mid, l, r) +
               queryRange(node * 2 + 1, mid + 1, end, l, r);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        LazySegTree st = new LazySegTree(arr);
        System.out.println(st.queryRange(0, 5));  // 输出: 36
        st.updateRange(2, 4, 5);
        System.out.println(st.queryRange(0, 5));  // 输出: 51
        System.out.println(st.queryRange(2, 4));  // 输出: 36
        st.updateRange(0, 5, 1);
        System.out.println(st.queryRange(0, 5));  // 输出: 57
    }
}