| title： 前缀和 |
| date： 2024-05-20 |
| tags： |
| - 数据结构 |
| categories： |
| - 数据结构 |
前缀和
什么是前缀和
前缀和是一种重要的预处理方法，能够极大降低查询的时间复杂度。它的基本思想是将一个数组的各个部分的和预先求出，保存在另一个数组中。
case
具体来说，假设我们有一个数组\(arr\)，那么前缀和数组prefixSum将会被定义为：\(prefixSum[i] = arr[0] + arr[1] + arr[2] + ... + arr[i]\)。也就是说，前缀和数组的每个元素，都是原数组中从第0个元素加到当前位置的元素之和。 例如，如果原数组为\([1, 2, 3, 4, 5]\)，对应的前缀和数组就是\([1, 3, 6, 10, 15]\)。
构造前缀和数组公式 \[ \begin{equation} \text{prefixSum}[i] = \sum_{j=0}^{i} \text{arr}[j] \tag{1.1} \end{equation} \]
求l到r区间和公式 \[ \begin{equation} \sum_{l,r} = \begin{cases} \text{prefixSum}[r], & \text{if } l = 0 \ \text{and} \ r = 0, \\ \text{prefixSum}[r] - \text{prefixSum}[l - 1], & \text{if } 0 < l \leq r. \end{cases} \tag{1.2} \end{equation} \]
优势
前缀和的主要作用是用于处理数组中不改变原数组的情况下区间和的问题，即快速求出数组中某个区间内的所有数之和。利用前缀和，我们可以将这个问题的时间复杂度从\(O(n)\)降低到\(O(1)\)。具体做法是：假设我们要求\([l, r]\)区间的和，那么只需要一次减法运算：\(prefixSum[r] - prefixSum[l - 1]\) 其中\((l > 0)\)就可以得到结果。如果\(l = 0\)，则区间和就是\(prefixSum[r]\)。
优化思路
不考虑边界情况,如果原数组为\([1, 2, 3, 4, 5]\)，对应的前缀和数组就是\([0, 1, 3, 6, 10, 15]\)。对应公式为： \[ \begin{equation} \text{prefixSum}[i] = \sum_{j=0}^{i} \text{arr}[j] \tag{2.1} \end{equation} \]
\[ \begin{equation} \sum_{l, r} = \text{prefixSum}[r + 1] - \text{prefixSum}[l], \text{ for } 0 < l \leq r. \tag{2.2} \end{equation} \]