## 举例

考虑数组 $a=[1,3,3,5,8]$，对其中的相邻元素两两作差（右边减左边），得到数组 $[2,0,2,3]$。然后在开头补上 $a[0]$，得到差分数组

$$d=[1,2,0,2,3]$$

这有什么用呢？如果从左到右累加 $d$ 中的元素，我们就「还原」回了 $a$ 数组 $[1,3,3,5,8]$。

这又有什么用呢？现在把连续子数组 $a[1],a[2],a[3]$ 都加上 $10$，得到 $a'=[1,13,13,15,8]$。再次两两作差，并在开头补上 $a'[0]$，得到差分数组 

$$d'=[1,12,0,2,-7]$$

对比 $d$ 和 $d'$，你会发现，对 $a$ 中连续子数组的操作，可以转变成对差分数组 $d$ 中**两个数**的操作。

## 定义和性质

对于数组 $a$，定义其**差分数组**（difference array）为

$$
d[i] =
\begin{cases} 
a[0],&i=0\\
a[i]-a[i-1],&i\ge 1
\end{cases}
$$

**性质 1**：从左到右累加 $d$ 中的元素，可以得到数组 $a$。

**性质 2**：如下两个操作是等价的。

- **区间操作**：把 $a$ 的子数组 $a[i],a[i+1],\ldots,a[j]$ 都加上 $x$。
- **单点操作**：把 $d[i]$ 增加 $x$，把 $d[j+1]$ 减少 $x$。特别地，如果 $j+1=n$，则只需把 $d[i]$ 增加 $x$。（$n$ 为数组 $a$ 的长度。）

利用性质 2，我们只需要 $\mathcal{O}(1)$ 的时间就可以完成数组 $a$ 上的区间操作。最后利用性质 1 从差分数组复原出数组 $a$。

## 代码模板

```py [sol-Python3]
# 你有一个长为 n 的数组 a，一开始所有元素均为 0。
# 给定一些区间操作，其中 queries[i] = [left, right, x]，
# 你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
# 返回所有操作执行完后的数组 a。
def solve(n: int, queries: List[List[int]]) -> List[int]:
    diff = [0] * n  # 差分数组
    for left, right, x in queries:
        diff[left] += x
        if right + 1 < n:
            diff[right + 1] -= x
    for i in range(1, n):
        diff[i] += diff[i - 1]  # 直接在差分数组上复原数组 a
    return diff
```

```java [sol-Java]
// 你有一个长为 n 的数组 a，一开始所有元素均为 0。
// 给定一些区间操作，其中 queries[i] = [left, right, x]，
// 你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
// 返回所有操作执行完后的数组 a。
int[] solve(int n, int[][] queries) {
    int[] diff = new int[n]; // 差分数组
    for (int[] q : queries) {
        int left = q[0], right = q[1], x = q[2];
        diff[left] += x;
        if (right + 1 < n) {
            diff[right + 1] -= x;
        }
    }
    for (int i = 1; i < n; i++) {
        diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
    }
    return diff;
}
```

```cpp [sol-C++]
// 你有一个长为 n 的数组 a，一开始所有元素均为 0。
// 给定一些区间操作，其中 queries[i] = [left, right, x]，
// 你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
// 返回所有操作执行完后的数组 a。
vector<int> solve(int n, vector<vector<int>> queries) {
    vector<int> diff(n); // 差分数组
    for (auto &q: queries) {
        int left = q[0], right = q[1], x = q[2];
        diff[left] += x;
        if (right + 1 < n) {
            diff[right + 1] -= x;
        }
    }
    for (int i = 1; i < n; i++) {
        diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
    }
    return diff;
}
```

```go [sol-Go]
// 你有一个长为 n 的数组 a，一开始所有元素均为 0。
// 给定一些区间操作，其中 queries[i] = [left, right, x]，
// 你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
// 返回所有操作执行完后的数组 a。
func solve(n int, queries [][]int) []int {
    diff := make([]int, n) // 差分数组
    for _, q := range queries {
        left, right, x := q[0], q[1], q[2]
        diff[left] += x
        if right+1 < n {
            diff[right+1] -= x
        }
    }
    for i := 1; i < n; i++ {
        diff[i] += diff[i-1] // 直接在差分数组上复原数组 a
    }
    return diff
}
```

```js [sol-JavaScript]
// 你有一个长为 n 的数组 a，一开始所有元素均为 0。
// 给定一些区间操作，其中 queries[i] = [left, right, x]，
// 你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
// 返回所有操作执行完后的数组 a。
function solve(n, queries) {
    let diff = new Array(n).fill(0); // 差分数组
    for (const q of queries) {
        const left = q[0], right = q[1], x = q[2];
        diff[left] += x;
        if (right + 1 < n) {
            diff[right + 1] -= x;
        }
    }
    for (let i = 1; i < n; i++) {
        diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
    }
    return diff;
}
```

## 练习

- [1094. 拼车](https://leetcode.cn/problems/car-pooling/)
- [1109. 航班预订统计](https://leetcode.cn/problems/corporate-flight-bookings/)
- [2381. 字母移位 II](https://leetcode.cn/problems/shifting-letters-ii/)
- [2406. 将区间分为最少组数](https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/)
- [2772. 使数组中的所有元素都等于零](https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/)
- [2528. 最大化城市的最小供电站数目](https://leetcode.cn/problems/maximize-the-minimum-powered-city/)

## 分类题单

[如何科学刷题？](https://leetcode.cn/circle/discuss/RvFUtj/)

1. [滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）](https://leetcode.cn/circle/discuss/0viNMK/)
2. [二分算法（二分答案/最小化最大值/最大化最小值/第K小）](https://leetcode.cn/circle/discuss/SqopEo/)
3. [单调栈（基础/矩形面积/贡献法/最小字典序）](https://leetcode.cn/circle/discuss/9oZFK9/)
4. [网格图（DFS/BFS/综合应用）](https://leetcode.cn/circle/discuss/YiXPXW/)
5. [位运算（基础/性质/拆位/试填/恒等式/思维）](https://leetcode.cn/circle/discuss/dHn9Vk/)
6. [图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）](https://leetcode.cn/circle/discuss/01LUak/)
7. [动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）](https://leetcode.cn/circle/discuss/tXLS3i/)
8. [常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）](https://leetcode.cn/circle/discuss/mOr1u6/)
9. [数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）](https://leetcode.cn/circle/discuss/IYT3ss/)
10. [贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）](https://leetcode.cn/circle/discuss/g6KTKL/)
11. [链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）](https://leetcode.cn/circle/discuss/K0n2gO/)
12. [字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）](https://leetcode.cn/circle/discuss/SJFwQI/)

[我的题解精选（已分类）](https://github.com/EndlessCheng/codeforces-go/blob/master/leetcode/SOLUTIONS.md)

欢迎关注 [B站@灵茶山艾府](https://space.bilibili.com/206214)


技术交流

举例
考虑数组 a=[1,3,3,5,8]，对其中的相邻元素两两作差（右边减左边），得到数组 [2,0,2,3]。然后在开头补上 a[0]，得到差分数组
d=[1,2,0,2,3]

这有什么用呢？如果从左到右累加 d 中的元素，我们就「还原」回了 a 数组 [1,3,3,5,8]。
这又有什么用呢？现在把连续子数组