前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。
例如，给定一个数组，要求计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和 ，其中 left <= right。
最直接的解法就是遍历 left 到 right 的所有项，返回它们累加的值。
但每进行一次这样的计算，都需要对数组进行遍历。在数组不变的前提下，这样的处理方式是低效的，它的时间复杂度是 O(N)，其中 N 代表 nums 数组的长度。
如果声明一个新的数组 preSum ，preSum[i] 记录 nums[0..i-1] 的累加和。此时如果想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。避免了每次进行 for 循环调用，求值的最坏时间复杂度为常数 O(1)。
值得注意的是，为了方便处理累加和， preSum 数组通常会比nums 数组多 1 项，preSum[0] 会初始化为 0 用作占位。
其实前缀和就是一个预处理的思想。如果需要在一个固定范围内，多次对范围内的全部或部分数据做相同的求值计算，都可以用到前缀和。类似的场景还有求数组内不同区间的最值、平均值等。