实验：Fenwick与线段聚合

从一次容器误用开始

先看场景：覆盖首尾索引、空区间、负值和连续更新测试。数据结构不是节点图鉴，而是调用者依赖的操作语义、内部表示和复杂度承诺。遇到结果错误、死循环、内存泄漏或性能陡降时，第一问不是“这是什么结构”，而是哪个公开操作违反了契约，哪条表示不变量首次失效，或哪种输入让原先的复杂度假设不成立。
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

本节核心机制是：实现Fenwick单点加/区间和和线段树点更新/范围最值。请把它拆成输入状态、操作步骤、输出/异常和保持的不变量。若只能说“用链表更快”“哈希是O(1)”，说明还没有把操作、前提和成本模型说完整。（唯一锚点：数据结构11-7《实验：Fenwick与线段聚合》。）
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

先写ADT契约与表示不变量

在纸上列公开值域、操作、前置条件、正常后置条件、失败后状态和迭代顺序。再列内部字段及不变量，例如size与可达节点数一致、数组有效区间连续、双链相邻互指、BST满足祖先范围、堆满足父子序、哈希探测不会在墓碑提前停止。调用者只能依赖契约，测试则要主动查看内部不变量。
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

关键边界是：不能调用第三方库；所有操作后用朴素数组作小规模对拍。把它改成最小操作序列：写出初态，每一步调用及返回，再画操作后的内部状态。边界测试不是额外装饰，而是验证空结构、单元素、重复值、容量临界、退化高度或非法索引下仍守住同一契约。（契约锚点：DS-11-07。）
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

分三轮把本节真正实现出来

第一步，先构造实验：Fenwick与线段聚合的最小表示，写出字段、初态和验证器，并用“覆盖首尾索引、空区间、负值和连续更新测试”中的最小正常输入跑通一条操作链。接着，依据“实现Fenwick单点加/区间和和线段树点更新/范围最值”逐指针、逐索引或逐父子关系执行变换，每一步记录size、容量、头尾、根、桶、父指针或候选集合，不允许直接跳到最终输出。最后，加入“不能调用第三方库；所有操作后用朴素数组作小规模对拍”对应的失败序列，检查返回值、异常、结构不变量和复杂度计数；修复后用不同规模和操作顺序再跑一次。（推进链唯一锚点：实验：Fenwick与线段聚合-11-7。）
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

跟我做一次操作与成本推演

固定输入和状态后，先画操作前结构，再为每个比较、索引、指针改写、元素移动或节点访问计数。假设本节有7个元素、每个元素触发7次题设基本操作，在不含扩容、缓存和对象分配的简化模型下共有 7×7=49 次。然后再问真实算法是否只访问全部元素一次、沿高度走一条路径，还是因嵌套/搬移访问平方数量。
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

Big-O必须对应操作和输入分布。最坏、均摊、期望、构建和查询成本不能混写。常数与缓存虽被渐进式隐藏，却会决定数组与链表在相同O(n)扫描下的真实差异。（推演锚点：实验：Fenwick与线段聚合。）

可运行实现与测试

代码题从标准输入读取操作日志并输出稳定结果，使用Python或C++17；不调用目标结构的标准库实现冒充核心算法。每题至少四组测试：正常、空/单元素、边界或退化、回归。测试既比较公开结果，也要让实现内部验证size、链接、范围、堆序、桶状态或分量数量。
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

你要补第五组测试，优先选择重复键、非法位置、扩容、删除后再插入、深链、相同优先级、非连通图或版本化恢复。随机性质测试需保存操作序列，不能靠不可复现的随机运行。（实现锚点：实验：Fenwick与线段聚合。）

常见错误与故障注入

主动打断一次更新：只改一半链接、扩容搬到一半、删除后留下墓碑错误、旋转后漏接父节点或迭代中修改结构。预测哪个不变量先失败，再让验证器定位。不要只在最终崩溃处修补；首个错误通常发生在更早的指针/索引写入顺序。

遇到性能问题也要做故障注入：给BST有序输入、哈希同桶键、动态数组固定增量扩容、图的稠密/稀疏极端。用操作计数而不是墙钟偶然波动证明复杂度变化。（错误锚点：实验：Fenwick与线段聚合。）

与前后结构建立联系

向前追问本节依赖的ADT、数组、链接或递归不变量，向后追问它怎样支持算法、索引、图或容器库。画三条因果箭头并注明操作复杂度。例如动态数组提供堆的连续完全树表示，堆提供优先队列语义，优先队列又成为后续图算法的候选边界。

同一个需求常有多个候选结构。列决策表比较查询、插入、删除、顺序、内存、缓存和最坏保证，不要只挑一个最小Big-O。（连接锚点：实验：Fenwick与线段聚合。）

在线练习与严格验收

每节至少绑定单选、多选和计算题，逐章另有真实实现题。单选先圈ADT操作与输入条件，多选逐项构造反例，计算题写原始操作计数，代码题通过全部测试并补退化序列。章节卷、期中、期末、实现与复杂度专项使用独立题池。

错题按契约、边界、不变量、指针/索引顺序、复杂度类型、迭代失效或键语义分类。更换数据规模和操作顺序重做，能在新序列下维护不变量才算学会。（练习锚点：实验：Fenwick与线段聚合。）

下课前闭卷自检

一，写实验：Fenwick与线段聚合的ADT操作。二，列内部字段和至少三个表示不变量。三，手推“实现Fenwick单点加/区间和和线段树点更新/范围最值”的更新顺序。四，为“覆盖首尾索引、空区间、负值和连续更新测试”补退化测试。五，解释“不能调用第三方库；所有操作后用朴素数组作小规模对拍”。六，分别写单次最坏与操作序列成本。七，说明何时应换另一种结构。
（长段唯一锚点：DS-11-07-实验：Fenwick与线段聚合。）

若答案仍是“用树更快”“哈希O(1)”“标准库有”，回到契约、状态图和操作计数。合格不是认出结构，而是能从空实现写出、验证、分析并迁移到真实工作负载。（自检锚点：实验：Fenwick与线段聚合。）