前缀和与差分

发表于 更新于 分类于 ， 阅读次数：
前缀和与差分是一种比较常用的预处理方法。对于后续的许多算法而言，使用前缀和和差分都能够有效地降低时间复杂度。当然，其本身也有许多奇妙的使用。

前缀和与差分，顾名思义，就是处理和差问题的一种方法。当然本文就从和差的角度展开，来谈一谈前缀和差分的使用。

前缀和最直白的应用就是区间和查询，差分最直白的应用就是区间值修改。这两部操作都是在 $O(1)$ 的时间复杂度下完成的。它们让反复求区间值的 $O(n)$ 的时间复杂度调整到了查询的复杂度之外，在多次查询的情况下时间复杂度表现极为优秀。因为懒的作图，所以用两张手写笔记截图来描述一下前缀和与差分的工作原理：

img

img

对于前缀和与差分更多的使用，[详见](【日报】差分与前缀和，但是加上了一些拓展 - 白色过膝袜 - 洛谷博客 (luogu.com.cn))