线段树的定义是？
考点：线段树的定义（A1）。
解析：线段树 = 二叉树，每个节点代表一个区间——根是全集、叶子是单元素。✅ 正确
排除法：无（判断题）。混淆点：与堆（完全二叉树+堆序）不同——线段树是区间树。
关联 · 区间划分（A5）：孩子区间怎么分。
线段树主要用于解决？
考点：线段树解决的问题（A2）。
解析：线段树解决区间查询 + 区间修改（和/最值等），单次 。✅ 正确
排除法：无（判断题）。混淆点：单点查找用数组即可；排序/字符串与线段树无关。
关联 · 应用场景总表（E6）：用途清单。
个元素做 次区间查询，暴力 ；线段树是？
考点：与暴力的对比（A3）。
解析：暴力 vs 线段树 ——、 都大时线段树碾压。✅ 正确
排除法：无（判断题）。混淆点： 小（如 1000 以内）暴力反而更好写。
关联 · 查询复杂度（B4）： 来源。
个元素的线段树通常开多大数组？
考点：节点数（A4）。
解析：最坏节点数不超过 ——数组开 保证不越界。✅ 正确
排除法：无（判断题）。混淆点： 为 2 的幂时恰 ，非 2 的幂时接近 。
关联 · 数组开小（H2）：开小的后果。
线段树中每个非叶节点的区间如何划分给孩子？
考点：区间划分（A5）。
解析：非叶节点从中间二分：左 、右 ——与元素值无关。✅ 正确
排除法：无（判断题）。混淆点：按值大小划分是 BST/堆的事，不是线段树。
关联 · mid 计算（D3）：二分实现。
判断题：线段树、树状数组、ST 表都能处理区间查询——但线段树功能最强（支持区间修改），代码量也最大。
考点：线段树与其他结构（A6）。
解析：三结构都能区间查询，线段树功能最强（区间修改）、代码量最大。✅ 正确
排除法：无（判断题）。混淆点：功能与代码量的权衡（G 组）。
关联 · 选择矩阵（G4）：怎么选。
build 建树的过程是？
考点：build 建树（B1）。
解析：build 递归——叶子取数组值、非叶先建孩子再合并。✅ 正确
排除法：无（判断题）。混淆点：合并 = pushup（B2），树的正确性靠它。
关联 · 建树过程输出（I2）：代码版。
判断题：pushup 是"用左右孩子的值更新父节点"——区间和树 pushup = 左和 + 右和，最值树 pushup = max(左, 右)。
考点：pushup 合并（B2）。
解析：pushup = 用孩子更新父节点——和树相加、最值树取 max。✅ 正确
排除法：无（判断题）。混淆点：pushup 是线段树唯一的"上传"通道。
关联 · pushup 遗漏（H4）：忘写的后果。
线段树区间查询的三种情况是？
考点：查询的三种情况（B3）。
解析：完全覆盖（直接返回）、完全不相交（返回中性值）、部分相交（递归孩子）。✅ 正确
排除法：无（判断题）。混淆点：三分支是线段树查询的骨架，缺一不可。
关联 · 查询三分支输出（J3）：代码版。
线段树单次区间查询的时间复杂度是？
考点：查询复杂度（B4）。
解析：每层最多访问约 4 个节点 → 。✅ 正确
排除法：无（判断题）。混淆点：不是 （除非完全覆盖直接返回）。
关联 · 与暴力的对比（A3）：复杂度优势。
线段树单点修改的过程是？
考点：单点修改（B5）。
解析：递归到叶子 → 更新 → 回溯沿路径 pushup。✅ 正确
排除法：无（判断题）。混淆点：只改叶子不改父 = 树坏了（P4）。
关联 · 单点修改输出（K1）：代码版。
数组 {1, 3, 5, 7}（下标 1 起），区间 的和是？
考点：区间和查询（B6）。
解析： 的 和 = 。✅ 正确
排除法：无（判断题）。混淆点：直接手算验证线段树查询结果。
关联 · 区间和查询（J1）：代码版。
线段树建树的时间复杂度是？
考点：建树复杂度（B7）。
解析：每个节点恰好处理一次 → 。✅ 正确
排除法：无（判断题）。混淆点：不是 ——节点数 而非 层各 。
关联 · 节点数（A4）：复杂度依据。
判断题：不用 lazy 直接递归到每个叶子做区间修改，单次 —— 次就是 ，与暴力无异，必须用 lazy 优化。
考点：朴素区间修改的问题（C1）。
解析：递归到每个叶子改 = 单次 、 次 ——与暴力无异。✅ 正确
排除法：无（判断题）。混淆点：lazy 就是为救这个而生的。
关联 · lazy 标记思想（C2）：解决方案。
lazy 标记的核心思想是？
考点：lazy 标记思想（C2）。
解析：完全覆盖的节点只改值 + 打标记，等访问孩子时再下传——延迟更新。✅ 正确
排除法：无（判断题）。混淆点：lazy = "这笔账先记着，用到孩子再结算"。
关联 · pushdown 下传（C3）：结算动作。
pushdown 的作用是？
考点：pushdown 下传（C3）。
解析：pushdown = 父标记传给孩子（更新孩子值与标记）→ 清空父标记。✅ 正确
排除法：无（判断题）。混淆点：下传后父标记必须清零（否则重复加）。
关联 · lazy 下传输出（L2）：代码版。
判断题：带 lazy 的区间修改——完全覆盖时更新节点值并累加标记；部分相交时先 pushdown 再递归修改，最后 pushup。
考点：带 lazy 的区间修改（C4）。
解析：完全覆盖改值打标记；部分相交先 pushdown 再递归、回来 pushup。✅ 正确
排除法：无（判断题）。混淆点：pushdown 在递归前、pushup 在递归后。
关联 · 区间加输出（L1）：代码版。
判断题：带 lazy 的区间查询，进入部分相交的孩子前必须先 pushdown——否则孩子值是"过期"的。
考点：带 lazy 的区间查询（C5）。
解析：进入部分相交的孩子前必须 pushdown——否则读到过期值。✅ 正确
排除法：无（判断题）。混淆点：这是 lazy 树查询与普通树查询的唯一区别。
关联 · lazy 忘下传（H1）：忘写的后果。
判断题：多次区间加可以合并成一个 lazy 标记（累加）——同一节点的标记叠加不破坏正确性。
考点：lazy 的累加性（C6）。
解析：多次区间加合并成累加标记——同节点标记叠加不破坏正确性。✅ 正确
排除法：无（判断题）。混淆点：区间覆盖是赋值标记（不累加），两者不同（E4）。
关联 · 区间覆盖（E4）：赋值标记。
带 lazy 的区间修改单次复杂度是？
考点：区间修改复杂度（C7）。
解析：带 lazy 的区间修改 ——只动完全覆盖的节点。✅ 正确
排除法：无（判断题）。混淆点：朴素版 、lazy 版 。
关联 · 朴素区间修改的问题（C1）：对比。
线段树数组开 的原因是？
考点：数组大小 4n（D1）。
解析：最坏节点数接近 ——开 保平安。✅ 正确
排除法：无（判断题）。混淆点： 在 非 2 的幂时不够（P2）。
关联 · 数组开小（H2）：错误示范。
线段树常用下标 1 起，根为 1，左右孩子是？
考点：下标 1 起（D2）。
解析：根为 1，孩子 、——二叉堆式编号。✅ 正确
排除法：无（判断题）。混淆点：下标 0 起要改公式（孩子 、）。
关联 · 树结构下标（I3）：代码版。
区间 的中点 mid 的标准写法是？
考点：mid 计算（D3）。
解析：mid = (l + r) >> 1——小数据无碍；大数据防溢出用 l + (r - l) / 2（P5）。✅ 正确
排除法：无（判断题）。混淆点：>> 1 对非负整数等价除 2。
关联 · mid 写法（P5）：溢出陷阱。
build/单点修改递归的出口条件是？
考点：递归出口（D4）。
解析：l == r（叶子）——区间长度 1 直接处理。✅ 正确
排除法：无（判断题）。混淆点：出口必须精确，否则死递归或越界。
关联 · build 填空（O1）：出口填空。
查询区间 完全覆盖节点区间 的判断是？
考点：完全覆盖判断（D5）。
解析：ql <= l && r <= qr——节点被查询区间包含。✅ 正确
排除法：无（判断题）。混淆点：方向反（节点包含查询）是经典错误（P3）。
关联 · 区间判断写反（H3）：错误示范。
部分相交时递归左孩子的条件是？
考点：相交判断（D6）。
解析：递归左孩子的条件 ql <= mid（查询区间与左孩子 有交）。✅ 正确
排除法：无（判断题）。混淆点：右孩子对称用 mid < qr。
关联 · 查询三分支（B3）：部分相交的展开。
判断题：线段树数组下标与区间一一对应——节点 存区间 的值， 由递归参数确定。
考点：内存与下标关系（D7）。
解析：节点下标 k 与区间 [l, r] 由递归参数绑定——k 是"地址"、[l,r] 是"内容"。✅ 正确
排除法：无（判断题）。混淆点：同一 k 在不同调用里对应不同区间——靠参数传递。
关联 · 树结构下标（I3）：下标规律。
线段树求区间最大值：叶子存元素值，pushup 是？
考点：区间最值（E1）。
解析：最值树 pushup = max(左, 右)——与和树只差合并函数。✅ 正确
排除法：无（判断题）。混淆点：中性值也不同（和用 0、最值用 -∞/0 视题意）。
关联 · 区间最值查询（J2）：代码版。
线段树求区间和：查询不相交时返回的中性值是？
考点：区间和（E2）。
解析：和树不相交返回 0——加法的中性元。✅ 正确
排除法：无（判断题）。混淆点：中性元选择是三分支正确性的细节。
关联 · 区间和统计（N1）：应用版。
判断题：区间加用 lazy——完全覆盖时 tree[k] += x × 区间长度、lazy[k] += x。
考点：区间加（E3）。
解析：完全覆盖时 tree[k] += x × len、lazy[k] += x——长度乘值。✅ 正确
排除法：无（判断题）。混淆点：忘记乘区间长度是高频 bug。
关联 · 区间加输出（L1）：代码版。
区间覆盖（全部赋值为 x）与区间加的区别是？
考点：区间覆盖（E4）。
解析：覆盖 = 赋值标记（tree[k] = x × len、lazy[k] = x），加 = 累加标记——语义不同。✅ 正确
排除法：无（判断题）。混淆点：覆盖下传是"赋值"不是"加"。
关联 · 区间覆盖输出（L5）：代码版。
判断题：同时支持区间加与区间乘时，需要两个 lazy 标记（加法标记与乘法标记），下传时按"先乘后加"的顺序更新。
考点：多 lazy（E5）。
解析：加与乘两个标记，下传按"先乘后加"——乘时加标记也要乘。✅ 正确
排除法：无（判断题）。混淆点：顺序错了值就错。
关联 · 多 lazy 输出（M3）：代码版。
判断题：线段树应用总表——区间和/区间最值/区间加/区间覆盖/区间乘、扫描线求面积、权值线段树求第 k 小。
考点：应用场景总表（E6）。
解析：和/最值/加/覆盖/乘、扫描线面积、权值线段树第 k 小——用途总表。✅ 正确
排除法：无（判断题）。混淆点：S 组完善程序高频考区间加求和。
关联 · 线段树解决的问题（A2）：用途总览。
动态开点线段树解决什么问题？
考点：动态开点（F1）。
解析：值域 时按需创建节点——只开访问到的节点。✅ 正确
排除法：无（判断题）。混淆点：用指针/数组模拟，空间 。
关联 · 离散化（F2）：另一种压缩值域的手段。
判断题：值域大但元素少时先离散化（把值映射到 的排名），再建线段树——压缩值域。
考点：离散化（F2）。
解析：大值域少元素 → 先离散化（值映射到排名）再建树。✅ 正确
排除法：无（判断题）。混淆点：离散化保持大小关系、不保持差值。
关联 · 离散化输出（N3）：代码版。
权值线段树是？
考点：权值线段树（F3）。
解析：叶子按值开、节点存值域内元素个数——可求第 k 小。✅ 正确
排除法：无（判断题）。混淆点：普通线段树叶子按位置。
关联 · 逆序对统计（N4）：权值树应用。
判断题：可持久化线段树（主席树）保存每次修改的历史版本——新版本共享未修改的节点。
考点：可持久化思想（F4）。
解析：主席树保存每次修改的历史版本——新版本共享未改节点。✅ 正确
排除法：无（判断题）。混淆点：空间 而非每版本 。
关联 · 线段树变体（F6）：变体谱系。
判断题：线段树合并 = 两棵线段树对应节点合并（如统计和）——用于树上统计等场景。
考点：线段树合并思想（F5）。
解析：两棵线段树对应节点合并（求和/取 max）——树上统计用。✅ 正确
排除法：无（判断题）。混淆点：合并复杂度与公共节点数相关。
关联 · 线段树变体（F6）：变体谱系。
判断题：线段树变体总表——动态开点（大值域）、离散化（稀疏值域）、权值线段树（第 k 小）、可持久化（历史版本）、合并（树上统计）。
考点：变体总表（F6）。
解析：动态开点/离散化/权值树/可持久化/合并——五大变体按需选。✅ 正确
排除法：无（判断题）。混淆点：变体是"同一棵树的不同用法"。
关联 · 线段树与其他结构（G 组）：选型。
线段树与树状数组的对比，正确的是？
考点：与树状数组（G1）。
解析：树状数组代码短常数小，但只支持前缀型操作；线段树全面（区间修改/最值）。✅ 正确
排除法：无（判断题）。混淆点：区间最值树状数组做不了（可差分才支持）。
关联 · 选择矩阵（G4）：选型依据。
线段树与 ST 表的对比，正确的是？
考点：与 ST 表（G2）。
解析：ST 表静态（不支持修改）、查询 ；线段树动态。✅ 正确
排除法：无（判断题）。混淆点：静态 RMQ 首选 ST 表。
关联 · 复杂度对比表（G5）：数字对比。
判断题：分块是线段树的"平替"——实现简单、复杂度 ，小数据下常比线段树好写。
考点：与分块（G3）。
解析：分块实现简单、——小数据下比线段树好写。✅ 正确
排除法：无（判断题）。混淆点：分块是"暴力 + 预处理"的折中。
关联 · 选择矩阵（G4）：选型依据。
需要区间加 + 区间求和，最佳选择是？
考点：选择矩阵（G4）。
解析：区间加 + 区间和 → 线段树（lazy）或树状数组（差分）。✅ 正确
排除法：无（判断题）。混淆点：ST 表不支持修改，直接排除。
关联 · 线段树解决的问题（A2）：矩阵落点。
判断题：复杂度对比——线段树建树 、查询/修改 ；树状数组 ；ST 表建表 、查询 （静态）。
考点：复杂度对比表（G5）。
解析：线段树建 查改 ；树状数组 ；ST 表建 查 。✅ 正确
排除法：无（判断题）。混淆点：ST 表的 以"静态"为代价。
关联 · 与树状数组（G1）/ 与 ST 表（G2）：数字依据。
判断题：选择依据——要修改选线段树/树状数组；只查询最值且静态选 ST 表；求第 k 小选权值线段树；值域大用离散化/动态开点。
考点：综合（G6）。
解析：要修改选线段树/树状数组；静态最值选 ST 表；第 k 小选权值树；大值域离散化。✅ 正确
排除法：无（判断题）。混淆点：选型四问——改不改、静态动态、什么操作、值域多大。
关联 · 选择矩阵（G4）：选型流程。
判断题：区间修改打了 lazy 后，查询/修改进入子区间前必须 pushdown——忘下传会读到过期的孩子值。
考点：lazy 忘下传（H1）。
解析：进入子区间前不 pushdown → 读到过期孩子值 → 结果错。✅ 正确
排除法：无（判断题）。混淆点：lazy 树的头号 bug（P1 实测输出 1 而非 3）。
关联 · lazy 忘 pushdown（P1）：错误示范。
判断题：线段树数组开 可能不够（最坏接近 节点）——开小会越界产生未定义行为。
考点：数组开小（H2）。
解析： 可能不够（最坏接近 ）——越界写坏内存。✅ 正确
排除法：无（判断题）。混淆点：越界是静默错误，难排查。
关联 · 数组大小 4n（D1）：正确大小。
判断题：完全覆盖判断 ql <= l && r <= qr 与"节点被查询区间包含"——写成反向（节点包含查询区间）是经典错误。
考点：区间判断写反（H3）。
解析：完全覆盖是"节点被查询包含"（ql <= l && r <= qr）——反向写错。✅ 正确
排除法：无（判断题）。混淆点：P3 实测反向判断输出 16（全树和）而非 8。
关联 · 完全覆盖判断（D5）：正确方向。
判断题：修改/下传后忘了 pushup 会导致父节点值不更新——查询结果错误且难排查。
考点：pushup 遗漏（H4）。
解析：修改/下传后忘 pushup → 父节点值不更新 → 查询错。✅ 正确
排除法：无（判断题）。混淆点：P4 实测叶子改了但树根还是 16。
关联 · pushup 合并（B2）：上传纪律。
判断题：以下结论全部正确——"线段树节点 ≤ 4n；查询三分支；lazy 延迟下传；部分相交递归前先 pushdown、返回前 pushup；下标 1 起孩子 2k/2k+1"。
考点：综合判断（H5）。
解析：五结论全对——4n、下标 1 起、三分支、lazy 时序、mid 写法。✅ 正确
排除法：无（判断题）。混淆点：本章核心模板要点收官自查。
关联 · 本章全部核心结论：收官综合判断题。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int n = 5; 05 cout << 4 * n; // 线段树数组安全大小 06 return 0; 07}
单选题：程序输出是？
考点：节点数与数组大小（I1）。
解析： → 数组开 。正确答案 A。
实现要点：线段树数组统一开 4 * n（最坏节点数不超过 4n）。手算：直接乘。
排除法：B 是 n；C 是 2n（可能不够）；D 是 n²。
关联 · 数组大小 4n（D1）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; // 下标 1~4 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; // pushup：区间和 11} 12int main() { 13 build(1, 1, 4); 14 for (int i = 1; i <= 7; i++) cout << tree[i] << " "; 15 return 0; 16}
单选题：程序输出是？（节点 1~7 的值，即整棵树）
考点：建树过程输出（I2）。
解析： 建树：tree[1]=16（全）、[2]=4（1+3）、[3]=12（5+7）、叶 1/3/5/7 → 16 4 12 1 3 5 7。正确答案 A。
实现要点：build 后序遍历——先建孩子再 pushup 求和。手算：递归画树。
排除法：B 左右子树值互换；C 层序错；D 叶序错。
关联 · build 建树（B1）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int k = 2; // 某节点下标 05 cout << 2 * k << " " << 2 * k + 1 << " " << k / 2; 06 return 0; 07}
单选题：程序输出是？（节点 2 的左右孩子与父节点下标）
考点：树结构下标（I3）。
解析：节点 2 的孩子 ，父 。正确答案 A。
实现要点：下标 1 起三公式——左 、右 、父 （整除）。手算：套公式。
排除法：B/C/D 无依据。
关联 · 下标 1 起（D2）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int left = 4, right = 12; // 左右孩子的值（区间和） 05 cout << left + right; // pushup：求和 06 return 0; 07}
单选题：程序输出是？（父节点 = 左 + 右）
考点：pushup 输出（I4）。
解析：——父 = 左和 + 右和。正确答案 A。
实现要点：和树 pushup = 加法；最值树 = max。手算：直接加。
排除法：B 是平均；C 是乘积；D 无依据。
关联 · pushup 合并（B2）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (______) { tree[k] = a[l]; return; } // 叶子出口 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12int main() { 13 build(1, 1, 4); 14 cout << tree[1]; 15 return 0; 16}
单选题：横线处应填入？（使输出为 16）
考点：建树填空（I5）。
解析：叶子出口 l == r。正确答案 A。
实现要点：build 出口 = 区间长度为 1。手算：验证 tree[1] = 16。
排除法：B 出口错（l>r 建不全）；C/D 无依据。
关联 · 递归出口（D4）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 // 区间 [1, 4] 的线段树：叶子 4 个，非叶 3 个，共 7 个节点 05 cout << 7; 06 return 0; 07}
单选题：程序输出是？（4 个元素恰为 2 的幂时节点数 = 2n - 1 = 7）
考点：结构综合（I6）。
解析：4 元素（2 的幂）节点数 = 。正确答案 A。
实现要点： 为 2 的幂时满二叉树结构。手算：4 叶 + 3 非叶。
排除法：B 是 2n；C 是 4n-1；D 无依据。
关联 · 节点数（A4）：特例。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12int query(int k, int l, int r, int ql, int qr) { 13 if (ql <= l && r <= qr) return tree[k]; // 完全覆盖 14 if (qr < l || r < ql) return 0; // 不相交 15 int mid = (l + r) >> 1; 16 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 17} 18int main() { 19 build(1, 1, 4); 20 cout << query(1, 1, 4, 2, 3); 21 return 0; 22}
单选题：程序输出是？（区间 [2,3] 的和）
考点：区间和查询（J1）。
解析：[2,3] = 3+5 = 8（三分支递归合并）。正确答案 A。
实现要点：查询三分支 = 覆盖返回、不相交返 0、部分相交递归求和。手算：验证 8。
排除法：B 是 [2,4]；C 是全和；D 无依据。
关联 · 查询的三种情况（B3）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = max(tree[2 * k], tree[2 * k + 1]); // 最值版 pushup 11} 12int query(int k, int l, int r, int ql, int qr) { 13 if (ql <= l && r <= qr) return tree[k]; 14 if (qr < l || r < ql) return 0; 15 int mid = (l + r) >> 1; 16 return max(query(2 * k, l, mid, ql, qr), query(2 * k + 1, mid + 1, r, ql, qr)); 17} 18int main() { 19 build(1, 1, 4); 20 cout << query(1, 1, 4, 2, 4); 21 return 0; 22}
单选题：程序输出是？（区间 [2,4] 的最大值）
考点：区间最值查询（J2）。
解析：[2,4] = max(3,5,7) = 7。正确答案 A。
实现要点：最值树 pushup = max、查询合并 = max。手算：三个元素取最大。
排除法：B 是和；C/D 无依据。
关联 · 区间最值（E1）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04int query(int k, int l, int r, int ql, int qr) { 05 if (ql <= l && r <= qr) { cout << "C"; return tree[k]; } // 完全覆盖 06 if (qr < l || r < ql) { cout << "N"; return 0; } // 不相交 07 cout << "P"; // 部分相交 08 int mid = (l + r) >> 1; 09 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 10} 11int main() { 12 cout << query(1, 1, 4, 2, 3) << " "; 13 return 0; 14}
单选题：程序输出是？（查询 [2,3] 访问节点的类型序列：根 P → 左 P → 左叶 N → 右叶 C → 右 P → 左叶 C → 右叶 N）
考点：查询三分支输出（J3）。
解析：访问序列 根P → 左P → 左叶N → 右叶C → 右P → 左叶C → 右叶N = PPNCPCN，结果 8。正确答案 A。
实现要点：三分支访问模式——部分相交的节点继续分、覆盖/不相交即止。手算：画递归树标类型。
排除法：B/C/D 序列缺项。
关联 · 查询的三种情况（B3）：访问模式实证。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04int query(int k, int l, int r, int p) { 05 if (l == r) return tree[k]; 06 int mid = (l + r) >> 1; 07 if (p <= mid) return query(2 * k, l, mid, p); 08 else return query(2 * k + 1, mid + 1, r, p); 09} 10int main() { 11 cout << query(1, 1, 4, 3); 12 return 0; 13}
单选题：程序输出是？（第 3 个元素的值）
考点：单点查询（J4）。
解析：查第 3 个元素沿路下钻 → 5。正确答案 A。
实现要点：单点查询 = 二分下钻（p ≤ mid 走左）。手算：路径 1→3→6。
排除法：B 是区间和；C/D 无依据。
关联 · 单点修改（B5）：同路径的修改版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04int query(int k, int l, int r, int ql, int qr) { 05 if (______) return tree[k]; // 完全覆盖 06 if (qr < l || r < ql) return 0; 07 int mid = (l + r) >> 1; 08 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 09} 10int main() { 11 cout << query(1, 1, 4, 3, 4); 12 return 0; 13}
单选题：横线处应填入？（使输出为 12）
考点：查询填空（J5）。
解析：完全覆盖条件 ql <= l && r <= qr。正确答案 A。
实现要点：节点被查询区间包含。手算：[3,4] 在节点 3 处覆盖返回 12。
排除法：B 方向反（P3）；C/D 无依据。
关联 · 完全覆盖判断（D5）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04int query(int k, int l, int r, int ql, int qr) { 05 if (ql <= l && r <= qr) return tree[k]; 06 if (qr < l || r < ql) return 0; 07 int mid = (l + r) >> 1; 08 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 09} 10int main() { 11 cout << query(1, 1, 4, 1, 4) << " " << query(1, 1, 4, 2, 4); 12 return 0; 13}
单选题：程序输出是？（[1,4] 全区间与 [2,4] 的和）
考点：查询综合（J6）。
解析：[1,4] = 16（根直接覆盖）、[2,4] = 15。正确答案 A。
实现要点：全区间查询在根节点一步返回 。手算：3+5+7 = 15。
排除法：B/C/D 无依据。
关联 · 查询复杂度（B4）：覆盖即止。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void update(int k, int l, int r, int p, int v) { 13 if (l == r) { tree[k] += v; return; } // 叶子：值 += v 14 int mid = (l + r) >> 1; 15 if (p <= mid) update(2 * k, l, mid, p, v); 16 else update(2 * k + 1, mid + 1, r, p, v); 17 tree[k] = tree[2 * k] + tree[2 * k + 1]; // 回溯 pushup 18} 19int main() { 20 build(1, 1, 4); 21 update(1, 1, 4, 2, 2); // a[2] += 2 → 3 变 5 22 cout << tree[1]; 23 return 0; 24}
单选题：程序输出是？（修改后的总和）
考点：单点修改输出（K1）。
解析：a[2] += 2 → 3 变 5，总和 16 → 18。正确答案 A。
实现要点：单点修改 = 下钻到叶子 + 回溯 pushup。手算：更新路径 1→2→5。
排除法：B 是原值；C/D 无依据。
关联 · 单点修改（B5）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 18, 6, 12, 1, 5, 5, 7}; // a[2] 已 +2 后的树 04int query(int k, int l, int r, int ql, int qr) { 05 if (ql <= l && r <= qr) return tree[k]; 06 if (qr < l || r < ql) return 0; 07 int mid = (l + r) >> 1; 08 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 09} 10int main() { 11 cout << query(1, 1, 4, 1, 2); 12 return 0; 13}
单选题：程序输出是？（修改后 [1,2] 的和 = 1 + 5）
考点：修改后查询（K2）。
解析：[1,2] = 1 + 5 = 6。正确答案 A。
实现要点：改后查询验证树已同步。手算：tree[2] = 6。
排除法：B 是改前值；C/D 无依据。
关联 · 修改加查询组合（K5）：同法。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void update(int k, int l, int r, int p, int v) { 13 cout << k << " "; // 打印访问的节点 14 if (l == r) { tree[k] += v; return; } 15 int mid = (l + r) >> 1; 16 if (p <= mid) update(2 * k, l, mid, p, v); 17 else update(2 * k + 1, mid + 1, r, p, v); 18 tree[k] = tree[2 * k] + tree[2 * k + 1]; 19} 20int main() { 21 build(1, 1, 4); 22 update(1, 1, 4, 2, 2); 23 return 0; 24}
单选题：程序输出是？（修改 a[2] 时访问的节点路径）
考点：单点修改过程（K3）。
解析：修改 a[2] 访问路径 1 → 2 → 5。正确答案 A。
实现要点：单点修改路径 = 从根到目标叶的链（长 ）。手算：二分方向。
排除法：B 是 a[1] 的路径；C 是右子树；D 无依据。
关联 · 单点修改（B5）：路径视角。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04void update(int k, int l, int r, int p, int v) { 05 if (l == r) { tree[k] += v; return; } 06 int mid = (l + r) >> 1; 07 if (______) update(2 * k, l, mid, p, v); // 目标在左半 08 else update(2 * k + 1, mid + 1, r, p, v); 09 tree[k] = tree[2 * k] + tree[2 * k + 1]; 10} 11int main() { 12 update(1, 1, 4, 3, 1); // a[3] += 1 → 5 变 6 13 cout << tree[1]; 14 return 0; 15}
单选题：横线处应填入？（使输出为 17）
考点：修改填空（K4）。
解析：目标在左半判断 p <= mid。正确答案 A。
实现要点：二分下钻方向判断。手算：p=3、mid=2 → 走右。
排除法：B 方向反；C/D 无依据。
关联 · 单点修改输出（K1）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void update(int k, int l, int r, int p, int v) { 13 if (l == r) { tree[k] += v; return; } 14 int mid = (l + r) >> 1; 15 if (p <= mid) update(2 * k, l, mid, p, v); 16 else update(2 * k + 1, mid + 1, r, p, v); 17 tree[k] = tree[2 * k] + tree[2 * k + 1]; 18} 19int query(int k, int l, int r, int ql, int qr) { 20 if (ql <= l && r <= qr) return tree[k]; 21 if (qr < l || r < ql) return 0; 22 int mid = (l + r) >> 1; 23 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 24} 25int main() { 26 build(1, 1, 4); 27 update(1, 1, 4, 1, 10); // a[1] = 11 28 cout << query(1, 1, 4, 1, 4); 29 return 0; 30}
单选题：程序输出是？（a[1] 加 10 后总和）
考点：修改加查询组合（K5）。
解析：a[1] += 10 → 总和 26。正确答案 A。
实现要点：改后 pushup 使查询即时生效。手算：16+10。
排除法：B 忘了加；C/D 无依据。
关联 · 修改后查询（K2）：同法。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void update(int k, int l, int r, int p, int v) { 13 if (l == r) { tree[k] += v; return; } 14 int mid = (l + r) >> 1; 15 if (p <= mid) update(2 * k, l, mid, p, v); 16 else update(2 * k + 1, mid + 1, r, p, v); 17 tree[k] = tree[2 * k] + tree[2 * k + 1]; 18} 19int main() { 20 build(1, 1, 4); 21 update(1, 1, 4, 2, 2); // a[2] = 5 22 update(1, 1, 4, 4, 3); // a[4] = 10 23 cout << tree[1]; 24 return 0; 25}
单选题：程序输出是？（两次修改后总和 = 1+5+5+10）
考点：多次修改（K6）。
解析：a[2]+2、a[4]+3 → 总和 21。正确答案 A。
实现要点：多次单点修改各自下钻 pushup。手算：16+2+3。
排除法：B/C/D 无依据。
关联 · 单点修改（B5）：连续修改。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void update(int k, int l, int r, int p, int v) { 13 if (l == r) { tree[k] += v; return; } 14 int mid = (l + r) >> 1; 15 if (p <= mid) update(2 * k, l, mid, p, v); 16 else update(2 * k + 1, mid + 1, r, p, v); 17 tree[k] = tree[2 * k] + tree[2 * k + 1]; 18} 19int main() { 20 build(1, 1, 4); 21 update(1, 1, 4, 3, -2); // a[3] = 3 22 cout << tree[3] << " " << tree[1]; 23 return 0; 24}
单选题：程序输出是？（右子树和与总和）
考点：单点修改综合（K7）。
解析：a[3] -= 2 → 右子树和 10、总和 14。正确答案 A。
实现要点：减 = 加负数；右子树 [3,4] = 3+7。手算：12-2 = 10。
排除法：B 是改前；C/D 无依据。
关联 · 多次修改（K6）：负数修改。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20], lazy[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void update(int k, int l, int r, int ql, int qr, int v) { 13 if (ql <= l && r <= qr) { // 完全覆盖：打 lazy 14 tree[k] += v * (r - l + 1); 15 lazy[k] += v; 16 return; 17 } 18 int mid = (l + r) >> 1; 19 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 20 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 21 tree[k] = tree[2 * k] + tree[2 * k + 1]; 22} 23int main() { 24 build(1, 1, 4); 25 update(1, 1, 4, 1, 2, 2); // [1,2] 每个 +2 26 cout << tree[1]; 27 return 0; 28}
单选题：程序输出是？（区间 [1,2] +2 后总和 = 16 + 4）
考点：区间加输出（L1）。
解析：[1,2] +2 → 总和 16+4 = 20。正确答案 A。
实现要点：完全覆盖打 lazy——tree += v × len、lazy += v。手算：节点 2 完全覆盖。
排除法：B 是原值；C 只加 2；D 无依据。
关联 · 区间加（E3）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 20, 8, 12, 1, 3, 5, 7}; 04int lazy[20] = {0, 0, 2, 0, 0, 0, 0, 0}; // 节点 2 带 lazy +2 05void pushdown(int k, int l, int r) { 06 if (!lazy[k]) return; 07 int mid = (l + r) >> 1; 08 tree[2 * k] += lazy[k] * (mid - l + 1); 09 lazy[2 * k] += lazy[k]; 10 tree[2 * k + 1] += lazy[k] * (r - mid); 11 lazy[2 * k + 1] += lazy[k]; 12 lazy[k] = 0; 13} 14int main() { 15 pushdown(2, 1, 2); 16 cout << tree[4] << " " << tree[5] << " " << lazy[2]; 17 return 0; 18}
单选题：程序输出是？（下传后两个叶子值与节点 2 的 lazy）
考点：lazy 下传输出（L2）。
解析：下传后叶 3、5，节点 2 的 lazy 清零 → 3 5 0。正确答案 A。
实现要点：pushdown = 孩子值 += lazy × 孩子长度、孩子 lazy 累加、父 lazy 清零。手算：1+2、3+2。
排除法：B 忘了更新；C 忘了清零；D 无依据。
关联 · pushdown 下传（C3）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20], lazy[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void pushdown(int k, int l, int r) { 13 if (!lazy[k]) return; 14 int mid = (l + r) >> 1; 15 tree[2 * k] += lazy[k] * (mid - l + 1); 16 lazy[2 * k] += lazy[k]; 17 tree[2 * k + 1] += lazy[k] * (r - mid); 18 lazy[2 * k + 1] += lazy[k]; 19 lazy[k] = 0; 20} 21void update(int k, int l, int r, int ql, int qr, int v) { 22 if (ql <= l && r <= qr) { tree[k] += v * (r - l + 1); lazy[k] += v; return; } 23 pushdown(k, l, r); 24 int mid = (l + r) >> 1; 25 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 26 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 27 tree[k] = tree[2 * k] + tree[2 * k + 1]; 28} 29int query(int k, int l, int r, int ql, int qr) { 30 if (ql <= l && r <= qr) return tree[k]; 31 pushdown(k, l, r); 32 int mid = (l + r) >> 1; 33 int res = 0; 34 if (ql <= mid) res += query(2 * k, l, mid, ql, qr); 35 if (mid < qr) res += query(2 * k + 1, mid + 1, r, ql, qr); 36 return res; 37} 38int main() { 39 build(1, 1, 4); 40 update(1, 1, 4, 1, 2, 2); // [1,2] +2 41 cout << query(1, 1, 4, 1, 1); // 查 [1,1]（触发 pushdown） 42 return 0; 43}
单选题：程序输出是？（a[1] 加 2 后 = 3）
考点：区间加加查询（L3）。
解析：[1,2]+2 后查 [1,1]——pushdown 后叶 4 = 3。正确答案 A。
实现要点：查询进入子区间前 pushdown——读到新值。手算：1+2 = 3。
排除法：B 是旧值（忘 pushdown 的 P1）；C/D 无依据。
关联 · 带 lazy 的区间查询（C5）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20], lazy[20]; 04void update(int k, int l, int r, int ql, int qr, int v) { 05 if (ql <= l && r <= qr) { 06 tree[k] += v * (r - l + 1); 07 ______; // 累加 lazy 标记 08 return; 09 } 10 int mid = (l + r) >> 1; 11 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 12 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 13 tree[k] = tree[2 * k] + tree[2 * k + 1]; 14} 15int main() { 16 // 已建好的树 {0,16,4,12,1,3,5,7}，区间 [3,4] +1 17 int a[5] = {0, 1, 3, 5, 7}; 18 // 略去 build（直接给出树值） 19 tree[1] = 16; tree[2] = 4; tree[3] = 12; tree[4] = 1; tree[5] = 3; tree[6] = 5; tree[7] = 7; 20 update(1, 1, 4, 3, 4, 1); 21 cout << tree[1]; 22 return 0; 23}
单选题：横线处应填入？（使输出为 18）
考点：lazy 填空（L4）。
解析：lazy[k] += v——累加标记。正确答案 A。
实现要点：完全覆盖三步 = 改值、打标记、返回。手算：验证总和 18。
排除法：B 覆盖式赋值（丢历史）；C/D 无依据。
关联 · lazy 的累加性（C6）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20], cov[20]; // cov = 覆盖标记（-1 表示无标记） 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void assign(int k, int l, int r, int ql, int qr, int v) { 13 if (ql <= l && r <= qr) { 14 tree[k] = v * (r - l + 1); // 赋值：值 = v × 长度 15 cov[k] = v; 16 return; 17 } 18 int mid = (l + r) >> 1; 19 if (ql <= mid) assign(2 * k, l, mid, ql, qr, v); 20 if (mid < qr) assign(2 * k + 1, mid + 1, r, ql, qr, v); 21 tree[k] = tree[2 * k] + tree[2 * k + 1]; 22} 23int main() { 24 build(1, 1, 4); 25 assign(1, 1, 4, 3, 4, 0); // [3,4] 全部赋值为 0 26 cout << tree[1]; 27 return 0; 28}
单选题：程序输出是？（[3,4] 清零后总和 = 1 + 3 + 0 + 0）
考点：区间覆盖输出（L5）。
解析：[3,4] 清零 → 总和 1+3+0+0 = 4。正确答案 A。
实现要点：覆盖 = 赋值 tree = v × len（非累加）。手算：12 → 0。
排除法：B 是原值；C 只算右半；D 无依据。
关联 · 区间覆盖（E4）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20], lazy[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void pushdown(int k, int l, int r) { 13 if (!lazy[k]) return; 14 int mid = (l + r) >> 1; 15 tree[2 * k] += lazy[k] * (mid - l + 1); 16 lazy[2 * k] += lazy[k]; 17 tree[2 * k + 1] += lazy[k] * (r - mid); 18 lazy[2 * k + 1] += lazy[k]; 19 lazy[k] = 0; 20} 21void update(int k, int l, int r, int ql, int qr, int v) { 22 if (ql <= l && r <= qr) { tree[k] += v * (r - l + 1); lazy[k] += v; return; } 23 pushdown(k, l, r); 24 int mid = (l + r) >> 1; 25 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 26 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 27 tree[k] = tree[2 * k] + tree[2 * k + 1]; 28} 29int query(int k, int l, int r, int ql, int qr) { 30 if (ql <= l && r <= qr) return tree[k]; 31 pushdown(k, l, r); 32 int mid = (l + r) >> 1; 33 int res = 0; 34 if (ql <= mid) res += query(2 * k, l, mid, ql, qr); 35 if (mid < qr) res += query(2 * k + 1, mid + 1, r, ql, qr); 36 return res; 37} 38int main() { 39 build(1, 1, 4); 40 update(1, 1, 4, 1, 2, 2); // [1,2] +2 41 update(1, 1, 4, 2, 3, 1); // [2,3] +1（跨节点，触发 pushdown） 42 cout << query(1, 1, 4, 2, 2); 43 return 0; 44}
单选题：程序输出是？（a[2] = 3 + 2 + 1 = 6）
考点：lazy 综合（L6）。
解析：[1,2]+2 再 [2,3]+1（跨节点触发 pushdown）→ a[2] = 3+2+1 = 6。正确答案 A。
实现要点：跨节点修改必须先 pushdown 拆开标记。手算：逐次更新。
排除法：B 漏一次加；C/D 无依据。
关联 · 带 lazy 的区间修改（C4）：综合版。
01#include <bits/stdc++.h> 02using namespace std; 03int a[6] = {0, 1, 2, 3, 4, 5}; 04int tree[24], lazy[24]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void pushdown(int k, int l, int r) { 13 if (!lazy[k]) return; 14 int mid = (l + r) >> 1; 15 tree[2 * k] += lazy[k] * (mid - l + 1); 16 lazy[2 * k] += lazy[k]; 17 tree[2 * k + 1] += lazy[k] * (r - mid); 18 lazy[2 * k + 1] += lazy[k]; 19 lazy[k] = 0; 20} 21void update(int k, int l, int r, int ql, int qr, int v) { 22 if (ql <= l && r <= qr) { tree[k] += v * (r - l + 1); lazy[k] += v; return; } 23 pushdown(k, l, r); 24 int mid = (l + r) >> 1; 25 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 26 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 27 tree[k] = tree[2 * k] + tree[2 * k + 1]; 28} 29int query(int k, int l, int r, int ql, int qr) { 30 if (ql <= l && r <= qr) return tree[k]; 31 pushdown(k, l, r); 32 int mid = (l + r) >> 1; 33 int res = 0; 34 if (ql <= mid) res += query(2 * k, l, mid, ql, qr); 35 if (mid < qr) res += query(2 * k + 1, mid + 1, r, ql, qr); 36 return res; 37} 38int main() { 39 build(1, 1, 5); 40 update(1, 1, 5, 1, 3, 2); // [1,3] +2 → 6、9 41 update(1, 1, 5, 2, 4, 1); // [2,4] +1 → 6、5、7 42 cout << query(1, 1, 5, 1, 5); 43 return 0; 44}
单选题：程序输出是？（最终数组 {3,5,6,5,5} 的总和）
考点：区间加求和完整（M1）。
解析：{1,2,3,4,5}：[1,3]+2、[2,4]+1 → {3,5,6,5,5}，总和 24。正确答案 A。
实现要点：完整 lazy 线段树 = build + pushdown + 区间修改 + 区间查询四件套。手算：逐区间叠加。
排除法：B 是原和；C/D 无依据。
关联 · 区间加（E3）：完整模板实战。
01#include <bits/stdc++.h> 02using namespace std; 03int a[6] = {0, 1, 2, 3, 4, 5}; 04int tree[24], lazy[24]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = max(tree[2 * k], tree[2 * k + 1]); 11} 12void pushdown(int k) { 13 if (!lazy[k]) return; 14 tree[2 * k] += lazy[k]; lazy[2 * k] += lazy[k]; 15 tree[2 * k + 1] += lazy[k]; lazy[2 * k + 1] += lazy[k]; 16 lazy[k] = 0; 17} 18void update(int k, int l, int r, int ql, int qr, int v) { 19 if (ql <= l && r <= qr) { tree[k] += v; lazy[k] += v; return; } 20 pushdown(k); 21 int mid = (l + r) >> 1; 22 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 23 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 24 tree[k] = max(tree[2 * k], tree[2 * k + 1]); 25} 26int query(int k, int l, int r, int ql, int qr) { 27 if (ql <= l && r <= qr) return tree[k]; 28 pushdown(k); 29 int mid = (l + r) >> 1; 30 int res = 0; 31 if (ql <= mid) res = max(res, query(2 * k, l, mid, ql, qr)); 32 if (mid < qr) res = max(res, query(2 * k + 1, mid + 1, r, ql, qr)); 33 return res; 34} 35int main() { 36 build(1, 1, 5); 37 update(1, 1, 5, 1, 3, 2); // [1,3] +2 → {3,4,5,4,5} 38 cout << query(1, 1, 5, 1, 5); 39 return 0; 40}
单选题：程序输出是？（修改后的全局最大值）
考点：区间最值加修改（M2）。
解析：[1,3]+2 → {3,4,5,4,5}，全局最大 5。正确答案 A。
实现要点：最值树区间加——完全覆盖 tree[k] += v（不需乘长度，最值整体平移）。手算：逐值加后取 max。
排除法：B 是乘长度误算；C/D 无依据。
关联 · 区间最值（E1）：最值版 lazy。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 // 区间加与区间乘两个 lazy：先乘后加的顺序 05 // 节点值 v，乘标记 mul，加标记 add 06 // 乘 x 时：v = v*x, mul = mul*x, add = add*x 07 // 加 x 时：v = v+x*len, add += x 08 int v = 5, mul = 2, add = 3; 09 v = v * mul + add * 1; // 模拟"先乘后加"后的值（长度为 1） 10 cout << v; 11 return 0; 12}
单选题：程序输出是？（5 × 2 + 3）
考点：多 lazy 输出（M3）。
解析：——先乘后加。正确答案 A。
实现要点：多标记顺序：乘时 v *= x, mul *= x, add *= x；加时 v += x·len, add += x。手算：按序演算。
排除法：B 是先加后乘（5+3 再 ×2 = 16）；C/D 无依据。
关联 · 多 lazy（E5）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[24], lazy[24]; 04void pushdown(int k, int l, int r) { 05 if (!lazy[k]) return; 06 int mid = (l + r) >> 1; 07 tree[2 * k] += lazy[k] * (mid - l + 1); 08 lazy[2 * k] += lazy[k]; 09 tree[2 * k + 1] += lazy[k] * ______; // 右孩子长度 10 lazy[2 * k + 1] += lazy[k]; 11 lazy[k] = 0; 12} 13int main() { 14 // 验证 pushdown：节点区间 [1,4]，lazy = 3 15 tree[2] = 10; tree[3] = 20; lazy[1] = 3; 16 pushdown(1, 1, 4); 17 cout << tree[2] << " " << tree[3] << " " << lazy[1]; 18 return 0; 19}
单选题：横线处应填入？（使输出为 16 26 0——左右各加 3×2）
考点：实战填空（M4）。
解析：右孩子长度 (r - mid)。正确答案 A。
实现要点：pushdown 两孩子长度 = mid - l + 1 与 r - mid。手算：10+6 = 16、20+6 = 26。
排除法：B 是左长度；C 是全长度；D 无依据。
关联 · lazy 下传输出（L2）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20], lazy[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void update(int k, int l, int r, int ql, int qr, int v) { 13 if (ql <= l && r <= qr) { tree[k] += v * (r - l + 1); lazy[k] += v; return; } 14 int mid = (l + r) >> 1; 15 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 16 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 17 tree[k] = tree[2 * k] + tree[2 * k + 1]; 18} 19int main() { 20 build(1, 1, 4); 21 update(1, 1, 4, 4, 4, 3); // 只改 [4,4]（右边界） 22 cout << tree[1]; 23 return 0; 24}
单选题：程序输出是？（a[4] +3 后总和 = 16 + 3）
考点：区间修改边界（M5）。
解析：[4,4]+3 → 总和 19。正确答案 A。
实现要点：单点区间 [4,4] 沿右链下钻到叶。手算：16+3。
排除法：B 是原值；C/D 无依据。
关联 · 区间加输出（L1）：边界情形。
01#include <bits/stdc++.h> 02using namespace std; 03int a[6] = {0, 2, 4, 6, 8, 10}; 04int tree[24], lazy[24]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12void pushdown(int k, int l, int r) { 13 if (!lazy[k]) return; 14 int mid = (l + r) >> 1; 15 tree[2 * k] += lazy[k] * (mid - l + 1); 16 lazy[2 * k] += lazy[k]; 17 tree[2 * k + 1] += lazy[k] * (r - mid); 18 lazy[2 * k + 1] += lazy[k]; 19 lazy[k] = 0; 20} 21void update(int k, int l, int r, int ql, int qr, int v) { 22 if (ql <= l && r <= qr) { tree[k] += v * (r - l + 1); lazy[k] += v; return; } 23 pushdown(k, l, r); 24 int mid = (l + r) >> 1; 25 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 26 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 27 tree[k] = tree[2 * k] + tree[2 * k + 1]; 28} 29int query(int k, int l, int r, int ql, int qr) { 30 if (ql <= l && r <= qr) return tree[k]; 31 pushdown(k, l, r); 32 int mid = (l + r) >> 1; 33 int res = 0; 34 if (ql <= mid) res += query(2 * k, l, mid, ql, qr); 35 if (mid < qr) res += query(2 * k + 1, mid + 1, r, ql, qr); 36 return res; 37} 38int main() { 39 build(1, 1, 5); // {2,4,6,8,10} 和 30 40 update(1, 1, 5, 2, 4, 1); // [2,4] +1 → {2,5,7,9,10} 41 cout << query(1, 1, 5, 3, 5); 42 return 0; 43}
单选题：程序输出是？（[3,5] 的和 = 7 + 9 + 10）
考点：实战综合（M6）。
解析：{2,4,6,8,10}：[2,4]+1 → {2,5,7,9,10}，[3,5] 和 = 26。正确答案 A。
实现要点：跨节点修改 + 查询的完整链路。手算：7+9+10。
排除法：B 是原 [3,5] 和；C/D 无依据。
关联 · 区间加求和完整（M1）：另一组数据。
01#include <bits/stdc++.h> 02using namespace std; 03int a[6] = {0, 1, 2, 3, 4, 5}; 04int tree[24]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12int query(int k, int l, int r, int ql, int qr) { 13 if (ql <= l && r <= qr) return tree[k]; 14 if (qr < l || r < ql) return 0; 15 int mid = (l + r) >> 1; 16 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 17} 18int main() { 19 build(1, 1, 5); 20 cout << query(1, 1, 5, 2, 4); 21 return 0; 22}
单选题：程序输出是？（[2,4] 的和 = 2+3+4）
考点：区间和统计（N1）。
解析：[2,4] = 2+3+4 = 9。正确答案 A。
实现要点：线段树最基础用途——区间求和。手算：验证。
排除法：B 是总和；C 是 [3,5]；D 无依据。
关联 · 区间和（E2）：用途代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int a[6] = {0, 3, 1, 4, 1, 5}; 04int tree[24]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = max(tree[2 * k], tree[2 * k + 1]); 11} 12int query(int k, int l, int r, int ql, int qr) { 13 if (ql <= l && r <= qr) return tree[k]; 14 if (qr < l || r < ql) return 0; 15 int mid = (l + r) >> 1; 16 return max(query(2 * k, l, mid, ql, qr), query(2 * k + 1, mid + 1, r, ql, qr)); 17} 18int main() { 19 build(1, 1, 5); 20 cout << query(1, 1, 5, 1, 4); 21 return 0; 22}
单选题：程序输出是？（[1,4] 的最大值）
考点：区间最值统计（N2）。
解析：{3,1,4,1,5} [1,4] 最大 = 4。正确答案 A。
实现要点：RMQ 用途——max 合并。手算：4 最大。
排除法：B 是全局最大 5；C/D 无依据。
关联 · 区间最值（E1）：用途代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int a[3] = {100, 5, 99999}; 05 int b[3]; 06 for (int i = 0; i < 3; i++) b[i] = a[i]; 07 sort(b, b + 3); // {5, 100, 99999} 08 for (int i = 0; i < 3; i++) { 09 // 每个数的排名（1 起） 10 cout << lower_bound(b, b + 3, a[i]) - b + 1 << " "; 11 } 12 return 0; 13}
单选题：程序输出是？（离散化后的排名）
考点：离散化输出（N3）。
解析：{100,5,99999} → 排名 {2,1,3}。正确答案 A。
实现要点：离散化 = 排序 + 二分查排名（lower_bound）。手算：排序 {5,100,99999}。
排除法：B 是原序排名；C 是倒序；D 无依据。
关联 · 离散化（F2）：概念题代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 // 权值线段树思想：从左到右插入 a[i]，统计已插入中 > a[i] 的个数 05 int a[4] = {3, 1, 4, 2}; 06 long long cnt = 0; 07 for (int i = 0; i < 4; i++) { 08 for (int j = 0; j < i; j++) 09 if (a[j] > a[i]) cnt++; // 朴素版：每步查前面更大的 10 } 11 cout << cnt; 12 return 0; 13}
单选题：程序输出是？（{3,1,4,2} 的逆序对：{3,1}、{3,2}、{4,2}）
考点：逆序对统计（N4）。
解析：{3,1,4,2} 逆序对 (3,1)(3,2)(4,2) = 3。正确答案 A。
实现要点：权值线段树做法 = 从左到右插入、查询"大于当前值的已插入数"。手算：逐元素统计。
排除法：B/C/D 无依据。
关联 · 权值线段树（F3）：用途代码化。
01#include <bits/stdc++.h> 02using namespace std; 03int a[6] = {0, 1, 2, 3, 4, 5}; 04int tree[24]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = ______; // 区间和的 pushup 11} 12int main() { 13 build(1, 1, 5); 14 cout << tree[1]; 15 return 0; 16}
单选题：横线处应填入？（使输出为 15）
考点：应用填空（N5）。
解析：pushup 求和 tree[2k] + tree[2k+1]。正确答案 A。
实现要点：和树的合并函数。手算：验证总和 15。
排除法：B 是最值合并；C/D 无依据。
关联 · pushup 输出（I4）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int a[6] = {0, 5, 2, 8, 1, 9}; 04int tree[24]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = max(tree[2 * k], tree[2 * k + 1]); 11} 12int query(int k, int l, int r, int ql, int qr) { 13 if (ql <= l && r <= qr) return tree[k]; 14 if (qr < l || r < ql) return 0; 15 int mid = (l + r) >> 1; 16 return max(query(2 * k, l, mid, ql, qr), query(2 * k + 1, mid + 1, r, ql, qr)); 17} 18int main() { 19 build(1, 1, 5); 20 cout << query(1, 1, 5, 2, 5); 21 return 0; 22}
单选题：程序输出是？（[2,5] 的最大值 = max(2,8,1,9)）
考点：应用综合（N6）。
解析：{5,2,8,1,9} [2,5] 最大 = 9。正确答案 A。
实现要点：最值树 + 区间查询完整用途。手算：max(2,8,1,9)。
排除法：B 是 [2,4]；C/D 无依据。
关联 · 区间最值统计（N2）：同法双题。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { ______; return; } // 叶子取值 07 int mid = (l + r) >> 1; 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12int main() { 13 build(1, 1, 4); 14 cout << tree[1]; 15 return 0; 16}
单选题：横线处应填入？（使输出为 16）
考点：build 填空（O1）。
解析：叶子取值 tree[k] = a[l]。正确答案 A。
实现要点：叶子 = 数组对应元素。手算：验证 16。
排除法：B 赋 0；C 取 a[r]（叶子时 l==r 等价但语义不清）；D 无依据。
关联 · build 建树（B1）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04int query(int k, int l, int r, int ql, int qr) { 05 if (ql <= l && r <= qr) return tree[k]; 06 if (______) return 0; // 完全不相交 07 int mid = (l + r) >> 1; 08 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 09} 10int main() { 11 cout << query(1, 1, 4, 1, 2); 12 return 0; 13}
单选题：横线处应填入？（使输出为 4）
考点：query 填空（O2）。
解析：不相交条件 qr < l || r < ql。正确答案 A。
实现要点：区间无交集的对称判断。手算：[1,2] 查询验证。
排除法：B 方向反；C/D 无依据。
关联 · 查询的三种情况（B3）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20], lazy[20]; 04void pushdown(int k, int l, int r) { 05 if (!lazy[k]) return; 06 int mid = (l + r) >> 1; 07 tree[2 * k] += lazy[k] * (mid - l + 1); 08 lazy[2 * k] += lazy[k]; 09 tree[2 * k + 1] += lazy[k] * (r - mid); 10 lazy[2 * k + 1] += lazy[k]; 11 ______; // 清空父标记 12} 13int main() { 14 tree[2] = 10; tree[3] = 20; lazy[1] = 3; 15 pushdown(1, 1, 4); 16 cout << lazy[1]; 17 return 0; 18}
单选题：横线处应填入？（使输出为 0）
考点：pushdown 填空（O3）。
解析：lazy[k] = 0——清空父标记。正确答案 A。
实现要点：下传后父标记必须清零。手算：验证输出 0。
排除法：B 清错对象；C/D 无依据。
关联 · pushdown 下传（C3）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20], lazy[20]; 04void update(int k, int l, int r, int ql, int qr, int v) { 05 if (ql <= l && r <= qr) { 06 tree[k] += v * (r - l + 1); 07 lazy[k] += v; 08 ______; // 完全覆盖直接返回 09 } 10 int mid = (l + r) >> 1; 11 if (ql <= mid) update(2 * k, l, mid, ql, qr, v); 12 if (mid < qr) update(2 * k + 1, mid + 1, r, ql, qr, v); 13 tree[k] = tree[2 * k] + tree[2 * k + 1]; 14} 15int main() { 16 tree[1] = 16; tree[2] = 4; tree[3] = 12; tree[4] = 1; tree[5] = 3; tree[6] = 5; tree[7] = 7; 17 update(1, 1, 4, 1, 2, 2); 18 cout << tree[1]; 19 return 0; 20}
单选题：横线处应填入？（使输出为 20）
考点：区间修改填空（O4）。
解析：完全覆盖后 return。正确答案 A。
实现要点：覆盖即止——不再递归孩子。手算：验证总和 20。
排除法：B break 无意义；C 是部分相交才做；D 无依据。
关联 · 带 lazy 的区间修改（C4）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04void update(int k, int l, int r, int p, int v) { 05 if (l == r) { tree[k] += v; return; } 06 int mid = (l + r) >> 1; 07 if (p <= mid) update(2 * k, l, mid, p, v); 08 else update(2 * k + 1, mid + 1, r, p, v); 09 ______; // 回溯更新父节点 10} 11int main() { 12 update(1, 1, 4, 2, 2); 13 cout << tree[1]; 14 return 0; 15}
单选题：横线处应填入？（使输出为 18）
考点：单点修改填空（O5）。
解析：回溯 pushup tree[k] = tree[2k] + tree[2k+1]。正确答案 A。
实现要点：改完叶子沿路更新父。手算：18。
排除法：B 累加错位置；C/D 无依据。
关联 · 单点修改（B5）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[24]; 04void build(int k, int l, int r) { 05 if (l == r) { tree[k] = 1; return; } // 每个位置初始为 1 06 int mid = (l + r) >> 1; 07 build(2 * k, l, mid); 08 build(2 * k + 1, mid + 1, r); 09 tree[k] = tree[2 * k] + tree[2 * k + 1]; 10} 11int query(int k, int l, int r, int ql, int qr) { 12 if (ql <= l && r <= qr) return tree[k]; 13 if (qr < l || r < ql) return 0; 14 int mid = (l + r) >> 1; 15 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 16} 17int main() { 18 build(1, 1, 6); 19 cout << query(1, 1, 6, ______); 20 return 0; 21}
单选题：横线处应填入？（统计 [2,5] 中"有效位置"的个数，使输出为 4）
考点：应用填空（O6）。
解析：查询参数 2, 5——统计 [2,5] 有效位置数。正确答案 A。
实现要点：线段树统计"区间内个数"（每位置初始 1）。手算：4 个位置。
排除法：B 是 [1,6]；C/D 无依据。
关联 · 区间和统计（N1）：计数用途。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 1, 3, 5, 7}; 04int tree[20]; 05void build(int k, int l, int r) { 06 if (l == r) { tree[k] = a[l]; return; } 07 int mid = ______; // 中点 08 build(2 * k, l, mid); 09 build(2 * k + 1, mid + 1, r); 10 tree[k] = tree[2 * k] + tree[2 * k + 1]; 11} 12int main() { 13 build(1, 1, 4); 14 cout << tree[1]; 15 return 0; 16}
单选题：横线处应填入？（使输出为 16）
考点：综合填空（O7）。
解析：中点 (l + r) >> 1。正确答案 A。
实现要点：二分中点标准写法。手算：验证建树。
排除法：B 减法；C 不加除；D 左移（乘 2）。
关联 · mid 计算（D3）：填空版。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20], lazy[20]; 04int query(int k, int l, int r, int ql, int qr) { 05 if (ql <= l && r <= qr) return tree[k]; 06 // 错误：部分相交时忘了 pushdown(k, l, r) 07 int mid = (l + r) >> 1; 08 int res = 0; 09 if (ql <= mid) res += query(2 * k, l, mid, ql, qr); 10 if (mid < qr) res += query(2 * k + 1, mid + 1, r, ql, qr); 11 return res; 12} 13int main() { 14 // 节点 2 区间 [1,2] 带 lazy +2（tree[2] 已更新为 8，但孩子 4、5 还是旧值 1、3） 15 tree[1] = 20; tree[2] = 8; tree[3] = 12; tree[4] = 1; tree[5] = 3; tree[6] = 5; tree[7] = 7; 16 lazy[2] = 2; 17 cout << query(1, 1, 4, 1, 1); 18 return 0; 19}
单选题：程序输出是？（忘 pushdown 读到过期叶子值 1；正确应为 3）
考点：lazy 忘 pushdown（P1）。
解析：忘下传读到旧叶值 1（正确 3）。正确答案 A。
实现要点：查询/修改进子区间前必须 pushdown。手算：对比 1 与 3。
排除法：B 是正确值；C 是父值；D 无依据。
关联 · lazy 忘下传（H1）：错误示范。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int n = 100000; 05 int tree[2 * n]; // 错误：只开 2n 06 // 最坏情况节点数接近 4n——2n 会越界 07 cout << 2 * n; 08 return 0; 09}
判断题：线段树数组开 不够——最坏情况节点数接近 ，开小会越界写坏内存。
考点：数组开小（P2）。
解析： 不够——最坏接近 节点，越界写坏内存。✅ 正确
实现要点：统一开 4 * n。手算：n=5 时节点数可到 9（>2n=10？——n=5 时 4n=20 保险）。
排除法：无（判断题）。混淆点：越界是静默错误。
关联 · 数组开小（H2）：错误示范。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04int query(int k, int l, int r, int ql, int qr) { 05 if (l <= ql && qr <= r) return tree[k]; // 错误：方向反了（节点包含查询区间） 06 if (qr < l || r < ql) return 0; 07 int mid = (l + r) >> 1; 08 return query(2 * k, l, mid, ql, qr) + query(2 * k + 1, mid + 1, r, ql, qr); 09} 10int main() { 11 cout << query(1, 1, 4, 2, 3); 12 return 0; 13}
单选题：程序输出是？（判断方向反 → 根节点 [1,4] "包含"查询区间 [2,3]，直接返回全树和 16；正确应为 8）
考点：区间判断错（P3）。
解析：方向反 → 根节点"包含"查询区间直接返回 16（正确 8）。正确答案 A。
实现要点：完全覆盖 = 节点被查询区间包含（ql <= l && r <= qr）。手算：方向对照。
排除法：B 是正确值；C/D 无依据。
关联 · 区间判断写反（H3）：错误示范。
01#include <bits/stdc++.h> 02using namespace std; 03int tree[20] = {0, 16, 4, 12, 1, 3, 5, 7}; 04void update(int k, int l, int r, int p, int v) { 05 if (l == r) { tree[k] += v; return; } 06 int mid = (l + r) >> 1; 07 if (p <= mid) update(2 * k, l, mid, p, v); 08 else update(2 * k + 1, mid + 1, r, p, v); 09 // 错误：回溯时忘了 pushup 10} 11int main() { 12 update(1, 1, 4, 2, 2); // a[2] += 2 13 cout << tree[1]; 14 return 0; 15}
单选题：程序输出是？（叶子改了但父节点没更新——总和仍是旧值 16；正确为 18）
考点：pushup 忘写（P4）。
解析：叶子改了父没更新 → 总和仍 16（正确 18）。正确答案 A。
实现要点：回溯 pushup 不可省。手算：16 vs 18。
排除法：B 是正确值；C/D 无依据。
关联 · pushup 遗漏（H4）：错误示范。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int l = 1500000000, r = 1500000000; 05 // 错误写法：mid = (l + r) / 2 在 l+r 溢出时出错 06 // 安全写法：mid = l + (r - l) / 2 07 int mid1 = (l + r) / 2; // l+r = 3×10^9 溢出 int 范围 → 错误 08 int mid2 = l + (r - l) / 2; // 安全 09 cout << mid1 << " " << mid2; 10 return 0; 11}
单选题：程序输出是？（ 溢出 int 后 mid1 为负；mid2 正确）
考点：mid 写法（P5）。
解析： 溢出 → mid1 = -647483648；安全写法 mid2 = 1500000000。正确答案 A。
实现要点：大数据用 l + (r - l) / 2 防溢出。手算：int32 回绕。
排除法：B 是安全值；C 未溢出；D 无依据。
关联 · mid 计算（D3）：溢出陷阱。
判断题：以下结论全部正确——"数组开 4n；下标 1 起孩子 2k/2k+1；查询三分支；lazy 延迟下传、进入子区间前 pushdown、返回前 pushup；mid 用 (l+r)>>1（小数据）或 l+(r-l)/2（防溢出）"。
考点：综合判断（P6）。
解析：五结论全对——4n、下标 1 起、三分支、lazy 时序、mid 防溢出。✅ 正确
实现要点：本章模板要点收官自查——数据结构卷的实现细节全部落位。手算：逐条对照本章代码。
排除法：无（判断题）。混淆点：lazy 的 pushdown/pushup 时序是本卷最易错点。
关联 · 本章全部核心结论：收官综合判断题。