前缀和
前缀和是一种解决区间求和问题的辅助方法，前缀和只适用于固定区间（数组、树等），如果区间元素发生变化，则不适用，此时需要考虑树状数组、线段树等方式。
问题类型
常见的问题也是和DP一样，求最大/最小/方案数。
| 类型 | 题目 | 备注 |
|---|---|---|
| 前缀和+哈希 | LC 560 | 两数之和 思路 |
| 前缀和+二分 | LC 2389 | 利用前缀和数组单调非递减 |
| 距离和 | LC 2602 | 数学计算 |
| 异或前缀和 | LC 1310 | 求的是异或前缀和，表示异或结果 |
| 二维前缀和 | LC 304 | 表示以某个元素坐标为对角线的矩形 |
| 树前缀和 | LC 437 | 利用hash |
思考
- 前缀和通常留一个presum[0]的特例，用来避免特殊情况的判断。
- 区分正整数子序列问题（无顺序要求，可以排序之后求前缀和进行划分）和子数组（连续，只能使用滑动窗口划分），如2389
- 前缀和与子数组的关系：前缀和本身就是一个子数组（从0开始），前缀和之差也是一个子数组
- 前缀和与子序列的关系：前缀和表示了一个特定子序列的和
- 正整数前缀和数组往往是单调非递减的，可以使用二分来优化
- 一种瞬间检查所有子数组和的方法(two sum思路): 对每个前缀使用hash检查，并且把前缀加到hash中，这种方式可以在一次遍历过程中添加
- 注意与DP的联系：一些用前缀和求最大子数组/子序列的问题涉及到如何选择下标，可以使用前缀和解决，如LC 53和LC 221
差分
差分数组指的是数组中每个值后减前作差得到的结果
性质：
- 差分数组，从左至右累加O(n)，可以得到原始数组对应位置的值。
- 对于连续子数组所有元素的操作，等于对差分数组中连续子数组左右区间端点的操作（因为对于连续子数组内部，差分不变）
- 利用这个性质，可以实现O(1)时间的区间操作，即区间操作转换成2个单点操作
- 结合上一性质，可以方便地复原出原始数组
类比：
- 差分数组：微分
- 前缀和：积分
题目
考虑上下车问题及其变体 LC 253，LC 370
树状数组
树状数组适合于经常进行原始数据修改的区间和问题，它可以把查找变成对数的时间复杂度。
树状数组3个核心函数：lowbit/query/add
- 求前缀和的时候query一下左右边界
- query的时候使用lowbit
- add的时候使用lowbit
题目
LC 307 模版题
线段树
略(可参考后面的资料4.)
参考资料
- https://leetcode.cn/circle/discuss/mOr1u6/
- https://leetcode.cn/problems/range-sum-query-mutable/solutions/632515/guan-yu-ge-lei-qu-jian-he-wen-ti-ru-he-x-41hv
- https://lfool.github.io/LFool-Notes/algorithm/前缀后缀法.html
- https://lfool.github.io/LFool-Notes/algorithm/线段树详解.html
- https://blog.csdn.net/qq_40941722/article/details/104406126