以下是用树状数组维护进行区间修改和区间查询的模板

void add(ll p, ll x){
    for(int i = p; i <= n; i += i & -i)
        sum1[i] += x, sum2[i] += x * p;
}
void range_add(ll l, ll r, ll x){
    add(l, x), add(r + 1, -x);
}
ll ask(ll p){
    ll res = 0;
    for(int i = p; i; i -= i & -i)
        res += (p + 1) * sum1[i] - sum2[i];
    return res;
}
ll range_ask(ll l, ll r){
    return ask(r) - ask(l - 1);
}
————————————————
版权声明：本文为CSDN博主「bestsort」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/bestsort/article/details/80796531

---

根据推导式，需要维护d[i]和d[i]*i的前缀和。但是我觉得维护这两个的方式应该不一样。

1、用树状数组维护d[i]，只需要add(L,x)，add(R+1,-x)，这是因为，

对于[l,L-1]，前缀和不变；

对于[L,R]，前缀和增加x；

对于[R+1,n]，前缀和也不变。

所以根据这个性质可以进行区间修改。

---

2、但是维护d[i]i时，如果只add(L,x),add(R+1,-x)，即c[L和L的祖先]+=Lx，c[R+1和R+1的祖先]-=(R+1)*x，那么

对于[1,L-1]，前缀和不变；

对于[L,R]，前缀和增加L*x；

对于[R+1,n]，前缀和减少x*(R+1-L)。

因此，对于区间[R+1，n]来说，它的前缀和改变了。

并且，对于[L+1,R]，它们的前缀和只增加了Lx，但对于每一个元素，应该是要增加x*i(L+1<=i<=R)。

---

例：

设L=2,R=4,在执行add(L,x),add(R+1,-x)后，

i=1时，前缀和=d[1]*1

i=2时，前缀和=d[1]*1+(d[2]+x)*2=d[1]*1+d[2]*2+2x

i=3时，前缀和=d[1]*1+(d[2]+x)*2+d[3]*3=d[1]*1+d[2]*2+d[3]*3+2x

…………

但是，因为[L,R]内每个元素都增加x，所以应该是这样的：

i=1时，前缀和=d[1]*1

i=2时，前缀和=d[1]*1+(d[2]+x)*2=d[1]*1+d[2]*2+2x

i=3时，前缀和=d[1]*1+(d[2]+x)*2+(d[3]+x)*3=d[1]*1+d[2]*2+d[3]*3+5x

…………

---

所以我觉得这种维护d[i]*i的前缀和是错误的。

但是它就是正确的。

希望各位大佬帮忙解决。