前面的矩阵实现改变了同一组乘加的安排。还有一种选择：先增加一次工作，为之后很多次查询减少工作。多做的这一步什么时候值得？
预计用时：40 分钟。打开 规模与表示现场，从“查一次，还是查很多次”开始。
输入是一串数，例如每天的订单量。要查第 l 天到第 r 天之前的总量，直接遍历 [l,r) 即可。查一次很自然；若反复查许多区间，就会重复读取其中的大部分数据。
可以先保存前缀和 P：P[0]=0，P[1] 是第一项，P[2] 是前两项之和。于是区间和等于 P[r]−P[l]。
以 [3,1,4,1] 为例，P=[0,3,4,8,9]。区间 [1,3) 包含 1 与 4，查询得到 P[3]−P[1]=8−3=5。起止位置相同时是空区间，差为零。
教材实际构建 64 项输入，每次查询 16 项。逐项方案每次读取 16 个输入；前缀方案先读 64 项，再为每次查询读两个前缀值。两条路线都实际执行并核对输出。
先猜查询一次时谁读得更少，再把查询次数拖到 16。一次时是 16 对 66；16 次时是 256 对 96。这里的“读取更少”尚不等于“运行更快”，因为分配、前缀写入、算术与缓存也有成本。
额外的前缀表有 65 个 binary64 数，占 520 字节数据区。读者获得了更便宜的重复查询，同时接下维护这份准备结果的责任。
若第三天数据改变，后面的前缀和都可能受影响。对经常修改的数据，每次重建整张表可能抵消收益。可以考虑其他数据结构，但它们会引入自己的查询、更新和空间成本。
第一章的缓存问题因此又出现了：这份准备属于哪次输入，何时失效，过期后能否被误用？给一个快照建立索引很清楚，给不断变化的共享数据维护索引，需要更完整的更新协议。
若 n 是数据量、q 是查询数、每次平均读取 m 项，逐项扫描约需 q·m 次输入访问；前缀方案的准备是 O(n)，每次查询是 O(1)，总量为 O(n+q)。这个比较解释了重复次数为何重要。
大 O 提供增长结构，机器成本决定同一规模下的具体代价。前缀表若很大而查询随机，缓存行为仍值得观察；很小的数据和很少的查询，则可能让直接扫描更简单。
矩阵转置后复用、建立查找索引、为变换预先生成常量表，都有类似的前期成本。完整比较要写明会用多少次，能保存多久。
把输入改成 [3,1,4,1]，手工核对空区间、整个区间、最后一项，再用 prefixSums 与 rangeSum 验证。它们在 algorithms.js 中，采用左闭右开的区间。
再改变输入的一项，说明原前缀表为什么失效。设计一个读者不容易误用旧表的接口，例如将输入版本与前缀表一起保存。
还有一个数值边界：两个很大的近似前缀相减，可能暴露相消误差。精确实数恒等式成立，并不保证任何浮点输入都满足同样的误差要求。本实验使用小整数把这项影响隔开了。
接下来改变的将不只是准备时机，还包括 究竟保存哪些数据。