前缀和与差分（超详细！！！）

前缀和和差分是一类常用的算法，它们常常被用来优化一些区间操作的问题，如求区间和、区间最大值/最小值等等。下面我们将分别介绍前缀和和差分的定义、用法和常见问题。

## 前缀和

前缀和，顾名思义，就是把前面所有数的和都求出来，用一个数组存起来，以便之后的查询。

### 定义

给定一个长度为 $n$ 的序列 $a$，令 $s_i = \sum_{j=1}^{i}a_j$，则 $s$ 称为序列 $a$ 的前缀和数组。

### 用法

前缀和的主要作用是用 $O(1)$ 的时间复杂度求出一个区间 $[l,r]$ 的和，即 $s_r - s_{l-1}$。这是因为 $s_r$ 存储了序列从 $1$ 到 $r$ 的和，而 $s_{l-1}$ 存储了序列从 $1$ 到 $l-1$ 的和，因此区间 $[l,r]$ 的和可以通过两个前缀和相减计算得出。

前缀和的时间复杂度为 $O(n)$，因为需要遍历一遍序列求出前缀和数组。但是，如果有多个查询需要求区间和，那么使用前缀和可以将每次查询的时间复杂度降低到 $O(1)$。

### 代码实现

下面是使用前缀和求区间和的代码实现：

vector<int> a; // 原序列
vector<int> s(a.size() + 1); // 前缀和数组

// 计算前缀和
for (int i = 1; i <= a.size(); i++) {
    s[i] = s[i - 1] + a[i - 1];
}

// 查询区间 [l, r] 的和
int sum = s[r] - s[l - 1];

## 差分

差分和前缀和相反，它主要用来对区间进行修改。我们可以利用差分数组进行区间修改，并最终得到修改后的序列。

### 定义

给定一个长度为 $n$ 的序列 $a$，令 $d_i = a_i - a_{i-1}$（$d_1 = a_1$），则 $d$ 称为序列 $a$ 的差分数组。

### 用法

差分的主要作用是对区间进行修改。假设我们需要将区间 $[l,r]$ 的数加上 $k$，我们可以将差分数组的 $d_l$ 加上 $k$，将 $d_{r+1}$ 减去 $k$。这样，对差分数组求前缀和，就可以得到修改后的序列。

具体来说，我们可以按照以下步骤进行区间修改：

1. 对差分数组的 $d_l$ 加上 $k$；
2. 对差分数组的 $d_{r+1}$ 减去 $k$；
3. 对差分数组求前缀和，得到修改后的序列。

差分的时间复杂度为 $O(n)$，因为需要遍历一遍序列求出差分数组。但是，如果有多次区间修改需要进行，那么使用差分可以将每次修改的时间复杂度降低到 $O(1)$。

### 代码实现

下面是使用差分进行区间修改的代码实现：

vector<int> a; // 原序列
vector<int> d(a.size() + 1); // 差分数组

// 计算差分数组
for (int i = 1; i < a.size(); i++) {
    d[i] = a[i] - a[i - 1];
}

// 修改区间 [l, r]，将数加上 k
d[l] += k;
d[r + 1] -= k;

// 对差分数组求前缀和，得到修改后的序列
for (int i = 1; i < d.size(); i++) {
    a[i] = a[i - 1] + d[i];
}

## 常见问题

### 1. 差分数组的长度是多少？

差分数组的长度应该比原序列长度多 1，因为 $d_1 = a_1$。

### 2. 什么情况下使用前缀和？什么情况下使用差分？

如果需要进行多次区间查询，那么使用前缀和可以将每次查询的时间复杂度降低到 $O(1)$；如果需要进行多次区间修改，那么使用差分可以将每次修改的时间复杂度降低到 $O(1)$。

### 3. 前缀和和差分的本质区别是什么？

前缀和和差分都是用来优化区间操作的算法，它们的本质区别在于：

- 前缀和是通过预处理前缀和数组来优化区间查询；
- 差分是通过预处理差分数组来优化区间修改。

### 4. 前缀和和差分能否同时使用？

当然可以。如果需要同时进行区间查询和修改，我们可以先使用差分数组对区间进行修改，然后再对差分数组求前缀和，得到修改后的序列。