<p>前缀和数组需初始化为长度n+1，即prefix = [0] * (len(nums) + 1)，遍历i∈[0,n−1]设prefix[i+1] = prefix[i] + nums[i]；求闭区间[l,r]和用prefix[r+1] − prefix[l]。</p>
Python前缀和数组怎么初始化才不越界
前缀和数组 prefix 的长度必须是原数组长度加1，否则后续所有下标计算都会偏移或报 IndexError。常见错误是直接用 len(nums) 初始化，导致 prefix[i] 表示的是前 i 个元素和（i 从 1 开始），但访问 prefix[0] 时合法，prefix[len(nums)] 才是总和——这个设计是为了统一处理左闭右开区间。
正确做法是：
- 令
prefix = [0] * (len(nums) + 1) - 遍历
i从 0 到len(nums)-1，执行prefix[i+1] = prefix[i] + nums[i] - 求区间
[l, r]（闭区间）和时，写成prefix[r+1] - prefix[l]，不是prefix[r] - prefix[l-1]
差分数组怎么构造和还原，为什么不能直接改原数组
差分数组 diff 的核心作用是「批量区间增减」，它本身不是数据快照，而是变化的记录。如果直接在原数组上做多次 nums[l:r+1] = [x + val for x in nums[l:r+1]]，时间复杂度是 O(n) 每次，而差分能做到 O(1) 更新 + O(n) 最终还原。
关键点：
立即学习“Python免费学习笔记（深入）”；
- 差分数组长度和原数组一致：
diff = [0] * len(nums) - 初始化：先设
diff[0] = nums[0]，再对i从 1 到len(nums)-1，赋值diff[i] = nums[i] - nums[i-1] - 对区间
[l, r]加val：只改两处 ——diff[l] += val，若r+1 则 <code>diff[r+1] -= val - 还原原数组必须从左到右累加：
res[0] = diff[0]，然后res[i] = res[i-1] + diff[i]
前缀和与差分混用时常见的索引错位陷阱
前缀和依赖「多一位」，差分依赖「原长」，两者混用（比如先差分更新再用前缀和查）极易因索引偏移导致结果差 1 个元素或越界。典型错误是把差分还原后的数组直接当原数组喂给前缀和初始化逻辑，却忘了还原后长度没变，而前缀和仍需 +1 长度。
安全做法：
- 差分更新后，用独立变量保存还原结果，例如
updated_nums = reconstruct(diff) - 再基于
updated_nums重新构建前缀和：prefix = build_prefix(updated_nums)，不要复用旧prefix - 调试时打印
len(prefix)和len(nums)，确认前者恒为后者 +1；打印len(diff)应等于len(nums)
单次查询少于10次时，别硬套前缀和
前缀和优化本质是「空间换时间」，但 Python 中列表创建、内存分配、额外循环都有成本。如果只查 1～2 次区间和，直接 sum(nums[l:r+1]) 更快，尤其当 r-l 很小（比如平均长度
适用边界参考：
- 查询次数 ≥ 5 且区间跨度方差大 → 上前缀和
- 有频繁区间修改（非单点）→ 必须用差分，前缀和无法高效支持修改
- 内存敏感场景（如嵌入式模拟、超长稀疏数组）→ 差分比前缀和省空间，但还原代价高
真正卡住性能的往往不是算法选型，而是没意识到 sum() 在小切片上已经足够快，还执着“必须预处理”。
