02.00_前缀和与差分
前缀和与差分
前缀和
前缀和是一种预处理技术，用于快速计算数组或矩阵中某个区间或区域的元素之和。
特点
- 预处理时间：
或
- 查询时间：
- 适用于频繁查询区间和的场景
分类
| 一维静态前缀和 | 无修改区间查询 | 一维数组 |
| 一维动态前缀和 | 单点修改区间查询 | 一维树状数组 |
| 一维动态前缀和 | 区间修改区间查询 | 一维线段树 |
| 二维静态前缀和 | 无修改区间查询 | 二维数组 |
| 二维动态前缀和 | 单点修改区间查询 | 二维树状数组 |
差分
差分是前缀和的逆运算，主要用于处理区间增减的操作。
特点
- 区间修改时间：
- 单点查询时间：需要还原数组，
- 适用于频繁进行区间修改的场景
分类
| 一维静态差分 | 区间修改一次查询 | 一维数组 |
| 一维动态差分 | 区间修改单点查询 | 一维树状数组 |
| 二维静态差分 | 区间修改一次查询 | 二维数组 |
| 二维动态差分 | 区间修改单点查询 | 二维树状数组 |
应用场景对比
前缀和适合：
- 频繁查询区间和
- 数据不经常变化
- 需要快速的区间查询
差分适合：
- 频繁进行区间增减操作
- 数据经常变化
- 最终只需要得到修改后的结果
选择建议
- 如果查询操作远多于修改操作，选择前缀和
- 如果修改操作远多于查询操作，选择差分
- 如果修改和查询都很频繁，考虑动态方案（树状数组/线段树）
- 如果空间有限，优先考虑一维解法
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递谷歌等公司7个岗位 >