预处理

预处理是算法中的一种优化技术,通过在实际算法执行之前对输入数据进行某些预先计算,可以提高算法的效率。预处理的目标是通过提前计算一些信息减少算法运行时的重复计算或者缩小问题的的范围来简化问题的解决方案。 预处理作用之一是将一些原本需要在算法主循环中执行的操作提前处理,从而减少算法的时间复杂度。例如在循环中需要重复计算某个值,可以先将这个值算出,避免重复。本质是通过空间换时间的方式,去存储需要多次计算的信息,来避免在循环中多次重复计算。

前缀和数组

求区间L-R的和：sum[L-R]=presum[R]-presum[L-1]

差分数组

对差分数字求前缀和还原成原数组：因为差分数组的值是两两相邻的数的差值，所以差分数组前面的数加上差值就是原数组的值

对区间[L,R]修改K，a[L-R]:cf[L]+K,cf[R+1]-K