提示

这个视频讲解的比较清楚，可以配合观看 前缀和、差分 概念教学

前缀和、差分

• 前缀和：前缀和是一种重要的预处理手段，可以用于快速计算一个子数组的和。

前缀和

思路

• 前缀和可以简单理解为 数列的前 n 项的和
• 前缀和数组：pre_sum[i] = pre_sum[i-1] + arr[i]（数列的前 i 项的和）

1. 它的思路是，对于一个数组arr，我们创建一个前缀和数组prefixSum，其中prefix_sum[i]表示arr[0]到arr[i]的和。
2. 这样，当我们需要计算子数组arr[l]到arr[r]的和时，只需要计算prefix_sum[r] - prefix_sum[l- 1]即可。

做法

题目中一般会说明或隐含需要求区间值的条件

• 前缀和数组：prefix_sum[i] = prefix_sum[i-1] + arr[i]（数列的前 i 项的和）
• 当需要求一个区间的和的时候(如l-r)： sum = prefix_sum[r] - prefix_sum[l-1]（数列的l到r项的和）

应用场景

• 区间求和
• 统计问题
• 矩阵求和
• 优化动态规划

差分（difference）

思路

• 差分数组：diff[i] = arr[i] - arr[i-1]（数列的差分）

做法

1. 对于数组arr，我们创建一个差分数组diff，其中diff[i]表示arr[i]和arr[i-1]的差。
   diff[i] = arr[i] - arr[i-1]
2. 每次将变化值d，在差分数组中，加在区间首l，减在区间尾r
diff[l] += d
diff[r+1] -= d
   • r+1 可能出现数组越界问题，注意处理
3. 计算出原数组的值，通过差分数组的计算方式变形得出
   arr[i] = diff[i] + arr[i+1]