算法做题技巧：前缀和
什么是前缀
“前缀”是在计算机科学中广泛使用的一个数学术语。
从字面上解释，就是指一个数列或字符串中从左到右递增截取一部分的结果。具体来说，在某个数列或字符串 seqseqseq 中，如果我们固定两个位置 iii 和 j(i≤j)j(i \leq j)j(i≤j) ，那么从 seqseqseq 的第 111 项开始，仅截取第 iii 到 jjj 个元素所组成的新的子数列或子字符串，就被称为原数列或原字符串的“前缀”。
举例：对于序列 [1,3,5,−2,4][1,3,5,-2,4][1,3,5,−2,4] 来说，其前缀包括 [1],[1,3],[1,3,5],[1,3,5,−2][1], [1,3], [1,3,5],[1,3,5,-2][1],[1,3],[1,3,5],[1,3,5,−2] 。
唯独不包括[1,3,5,−2,4][1,3,5,-2,4][1,3,5,−2,4]这个序列本身。
什么是前缀和？
前缀和是一种数组存储和处理技术，它用于快速求取一个序列中任意连续区间的和。
换句话说，对于一个数列 a，长度为n，它的前缀和 s[i] 就是a[0], a[1], … , a[i-1]之和，默认情况下s[0]为0，可以理解为空序列的和为0。那么对于多次询问，可以用前缀和把每个询问的区间求和问题，变换成两个前缀和的差，即 (l,r) 区间和 = S[r]-S[l-1]。
例如：
给定数组a=[1, 3, 4, 8, 6, 1, 4, 2], 它的前缀和依次为s=[0, 1, 4, 8, 16, 22, 23, 27, 29]
有一个求区间 [3, 7] 和的操作，则可以通过前缀和 s 得到：s[8] - s[3] = 29 - 8 = 21
因此，preSum 数组可以通过如下方式计算得出：preSum[0] = 0，preSum[k] = preSum[k-1] + arr[k]（1≤k 前缀和的使用场景很多，比如在动态规划、数学运算，深度搜索等方面都会用到。
由于前缀和数组本身可以提前预处理，在具有大量子数组求和问题的场景中，前缀和也可以优化问题的时间复杂度。