区间加等差数列

· · 算法·理论

将一个区间 [l, r] 加上一个首项为 a，公差为 d 的等差数列。

离线修改，最后查询的

使用二阶差分，最后二阶前缀和回去就是原数组。

代码：

void add(int l, int r, int a, int d) {
    c[l] += a;
    c[l+1] += d-a;
    c[r+1] -= a+d*(r-l+1);
    c[r+2] += a+d*(r-l);
}

在线修改并查询的

可能需要线段树/树状数组？

就是维护原数列的一阶差分即可。

好像不太需要差分了？记得之前有一场 div1 的 B 就是需要区间加等差数列。

当时的做法好像是根据区间加等差数列是可以直接打 tag 的，所以维护 tag_a 和 tag_d 分别表示总的首项和公差，由于区间加两个等差数列是可以合并的：a1+k*d1 + a2+k*d2 = (a1+a2)+j*(d1+d2) 的。

题目链接是这个？

写的很抽象的代码