前缀和与差分
两组互逆的运算
简单说前缀和就是数列求和
差分就是逆过来
前缀和通常用于求某区间的和 （用类似等差数列的性质嘛 大的减小的 余下来的就是某段的累加和）
差分通常用于 想在前缀和数组中某段元素加减某个数
如果在前缀和数组中操作的话就要进行很多数的操作
而反过来用差分数组算的话 就只需要在起始出加减n然后在结束处补平就行了
核心在于insert函数部分
然后还要理解的一点就是 构造差分数组也可以使用insert
将原本的a3-a2变成 -a2+a3
这样就能明了很多
一维二维差别不大 细心捋一下 要对哪部分操作
💬 评论