区域和检索 - 数组不可变

定义 pre[k] 为前 k 个元素的和，并令 pre[0]=0。区间 [i,j] 的和等于 pre[j+1]−pre[i]。

初始化 pre[0]=0，表示不包含任何元素的空前缀。这样，左端点为 0 的查询也能使用同一条公式。

读取 nums[0]=2，准备计算 pre[1]。递推关系是 pre[k+1]=pre[k]+nums[k]。

pre[1]=pre[0]+nums[0]=0+2=2。右侧表格新增 pre[1]，表示第一个元素的和。

读取 nums[1]=4。已有 pre[1]=2，因此下一项是 2+4。

pre[2]=2+4=6，表示前两个元素的和。原数组不变，只更新前缀和数组。

读取 nums[2]=1，接着计算前 3 个元素的和。

pre[3]=6+1=7。前缀和下标 3 表示元素个数，对应原数组下标 0 到 2。

读取 nums[3]=3，接着计算前 4 个元素的和。

pre[4]=7+3=10。这个值包含原数组下标 0 到 3 的元素。

读取最后一个元素 nums[4]=5，计算 pre[5]。

pre[5]=10+5=15。长度为 5 的原数组，对应长度为 6 的前缀和数组。

前缀和数组为 [0,2,6,7,10,15]。构造过程遍历了原数组一次；后续查询直接读取这里的值。

查询 [1,3] 时，先取 pre[4]=10。绿色区域是下标 0 到 3，包含目标区间，也多包含了下标 0。

再减去 pre[1]=2。红色标出需要扣除的前缀，剩下的绿色区域恰好是下标 1 到 3。

两个前缀的公共部分抵消，得到 10−2=8。查询只需读取两个前缀和并相减，不必重新遍历区间。

查询整个数组 [0,4]，先取 pre[5]=15。此时目标区间从下标 0 开始。

左端点为 0，需要减去空前缀 pre[0]=0。无需为这种情况编写额外分支。

sumRange(0,4)=15−0=15，与整个数组的元素和一致。

再看含负数的数组 [2,-4,1,3,5]。前缀和为 [0,2,-2,-1,2,7]，查询 [1,3] 仍然使用相同公式。

取 pre[4]=2，再减去 pre[1]=2。虽然前缀和不再递增，两个前缀的公共部分仍能抵消。

sumRange(1,3)=2−2=0，也就是 −4+1+3。前缀和求区间和不要求数组元素非负。

整个数组、单个元素和含负数的数组都使用同一条公式。前提是查询端点合法，且数组未被修改。

补充理解：数组发生修改后可以重建前缀和，但单次更新最坏需要 O(n) 时间。频繁更新时可考虑树状数组或线段树。