1. 背景
假设现在有一个非常大的数组 arr，对数组里面的数字需要反复做两个操作：
1）随机的选择一块区间，然后对区间里面的所有数字求和。
2）随机修改数组里面的某一个值，即更新操作。
因为数组是随机存取的，所以更新操作很容易，其时间复杂度是 $O(1)$。
对于求和操作，其时间复杂度取决于区间的长度，假设区间长度为 $L$，则求和操作的时间复杂度为 $O(L)$。
那有没有办法降低求和操作的时间复杂度呢？
首先我们想到的是另外建立一个数组 sumArr，这个数组存储的是 arr 数组的前缀和，即
$$sumArr[i] = \sum_{j=0}^{i}arr[j]$$
未完待续。。。。。。
原文：https://www.cnblogs.com/yanghh/p/13660603.html