数组前缀

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。通常，求解某个数组区间的和需要遍历做累加，如果涉及到频繁多次求和，就会增加时间开销。

前缀和这种方法，一次遍历后构造前缀和数组，能以 O(1) 的时间求解数组的区间和。

常见有一维数组和二维数组两种使用方式。

例题1 区域和检索 - 数组不可变 力扣303

https://leetcode.cn/problems/range-sum-query-immutable/

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/xiao-er-me-f69af/

这道题常规思路是遍历求前缀和，时间复杂度是O(N)，但是有O(1)的方法：构造一个前缀和数组，构造完后无需遍历直接求解。

例题2 二维区域和检索 - 矩阵不可变 力扣304

https://leetcode.cn/problems/range-sum-query-2d-immutable/

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/xiao-er-me-f69af/

https://leetcode.cn/problems/range-sum-query-2d-immutable/solution/er-wei-qian-zhui-he-jian-dan-tui-dao-tu-sqekv/

常规思路还是遍历，但是会超时。较好的方法是参照上一题目的前缀和数组做。

对于使用前缀和求解，有两种方式：

1. 依然是从一维角度，构造时分别对矩阵的每一行做一个前缀和数组，然后计算时，遍历每一行，每行O(1)的时间做行和的累加，得到矩阵和。这样的时间是O(行数)。
2. 从二维角度，构造时对每个从(0,0)开始的矩形求前缀和，然后进行子矩阵前缀和的加减，这样每次求前缀和的时间只有O(1)。

差分数组

差分数组和前缀和思想非常类似，前缀和表示数组区间的和，而构造差分数组多用来表示不同数组区间的差值。主要适用场景是频繁对原始数组的某个区间的元素进行增减。

例题1 航班预订统计 力扣1109

https://leetcode.cn/problems/corporate-flight-bookings/

本题要抽象成差分数组做。

例题2 拼车 力扣1094

https://leetcode.cn/problems/car-pooling/

本题在纸上画一下车站和上下乘客容量，就能发现这也可以用差分数组做。需要注意：

1. 乘客在下车的站点就要把容量加上。
2. 注意题目条件，比如站台最大数量。