《线段树 1》

区间修改用树状数组差分维护即可。
区间查询,也就是求

\small \begin{aligned} a_1+a_2+a_3+\dots+a_n &= d_1+(d_1+d_2)+(d_1+d_2+d_3)+\dots+(d_1+d_2+d_3+\dots+d_n) \\ &= nd_1+(n-1)d_2+(n-2)d_3+\dots+d_n \\ &= n(d_1+d_2+d_3+\dots+d_n)-(d_2+2d_3+3d_4+\dots+(n-1)d_n) \end{aligned}

维护两个树状数组即可。

1 个赞

咋那么感觉讲了跟没讲一样
不会树状数组的人呢

1 个赞