P2357

· · 个人记录

个人Blog同步链接

题目传送门

与普通树状数组不同的是，这次既需要单点修改、区间查询，又需要区间修改、单点查询。

对于数组 a 的差分数组 d，我们可以使用 d 求出 a 的前缀和数组 s。

由于 d_k=a_k-a_{k-1}，则：

a_k=d_1+d_2+d_3+\cdots+d_k

那么：

\begin{aligned} s_k&=a_1+a_2+a_3+\cdots+a_k\\ &=d_1+(d_1+d_2)+(d_1+d_2+d_3)+\cdots+(d_1+d_2+d_3+\cdots+d_k)\\ &=k\times d_1+(k-1)\times d_2+(k-2)\times d_3+(k-3)\times d_4+\cdots+d_k\\ &=(k+1)(d_1+d_2+d_3+\cdots+d_k)-(1\times d_1+2\times d_2+3\times d_3+\cdots+k\times d_k)\\ &=(k+1)\sum_{i=1}^k d_i-\sum_{i=1}^k d_i\times i \end{aligned}

维护树状数组 d_i=a_i-a_{i-1} 和树状数组数组 c_i=d_i\times i 即可。

关于各个操作：

  1. 差分处理

  2. 由1同理

  3. 由1同理

  4. 计算前缀和

  5. 由4同理