树状数组 区间加 区间和 小记

树状数组 区间加 & 区间和 小记

考虑差分数组的变化，即 \(d_i=a_i-a_{i-1}\)。

那么区间加时，会使 \(d_l\gets d_l+val,d_{r+1}\gets d_{r+1}-val\)。

考虑求区间和，转化为求前缀的和，即求

\[\begin{aligned} \sum _{i=1}^r \sum _{j=1} ^i d_j &= \sum _{i=1}^rd_i(r-i+1) \\&= (r+1)\sum _{i=1}^r d_i -\sum _{i=1}^r d_i\times i \end {aligned} \]

因此维护 \(d_i,d_i\times i\) 的前缀和即可，需要使用两个树状数组。