樹狀數組 區間加 & 區間和 小記
樹狀數組 區間加 & 區間和 小記
考慮差分數組的變化，即 \(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\) 的前綴和即可，需要使用兩個樹狀數組。
浙公網安備 33010602011771號