前缀和与差分算法笔记

一、前缀和算法

1. 作用与目的

快速地求数组中任意区间的和

2. 算法思想

• 构建一个前缀和数组 s
• s[i] 表示 a 数组的前 i 项的总和

3. 举例说明

• a 数组：[5, 4, 1, 2, 3]
• 前缀和数组 s：
  • s[0] = 0
  • s[3] = a[1] + a[2] + a[3] = 10
  • s[5] = a[1] + a[2] + a[3] + a[4] + a[5] = 15

4. 核心公式

1. 前缀和数组计算：s[i] = s[i-1] + a[i]
2. 区间和计算：计算 a 数组从第 x 项到第 y 项的总和 = s[y] - s[x-1]

二、差分算法

1. 作用与目的

快速地修改数组中某一段区间的所有元素

2. 算法思想

利用差分数组快速完成对原数组的区间修改操作，通过修改差分数组的少量元素实现对原数组的批量修改

3. 核心定义与公式

1. 差分数组定义：c[i] = a[i] - a[i-1]
2. 区间修改公式：对 a 数组下标从 x 到 y 的值都加 k，只需修改：
   • c[x] += k
   • c[y+1] -= k
3. 还原原数组：a[i] = c[i] + a[i-1]（由差分数组定义推导而来）

4. 举例说明

• a 数组：[5, 4, 1, 3, 2]
• 差分数组计算：
  • c[2] = a[2] - a[1] = 4 - 5 = -1
  • c[4] = a[4] - a[3] = 3 - 1 = 2
• 原数组还原：
  • a[2] = c[1] + c[2]
  • a[3] = c[1] + c[2] + c[3]
  • 对差分数组求前缀和可得到原数组

5. 差分算法步骤

1. 通过原始数组 a 得到差分数组 c
2. 利用差分数组快速进行区间修改
3. 通过差分数组还原回原始数组 a
4. 按照题目要求对原始数组进行统计答案

三、代码实现（差分算法示例）