树状数组能维护的东西：单点修改，查前缀和。
树状数组 1 直接朴素前缀和，树状数组 2 就差分一下。
对于线段树 1 的操作，不好用一个树状数组维护。
首先得把区间加给变成单点加。将数组差分为 \(d\) 即可。
首先用一个树状数组维护 \(s_0(x)=\sum\limits_{i=1}^xd_i\)。
\[\begin{aligned} &\sum\limits_{i=l}^r\sum\limits_{j=1}^id_i\\ =&(r-l+1)\sum\limits_{i=1}^{l-1}d_i+\sum\limits_{i=l}^r(r-i+1)d_i\\ =&(r-l+1)s_0(l-1)+(r+1)\sum\limits_{i=l}^rd_i-\sum\limits_{i=l}^rd_ii\\ =&(r-l+1)s_0(l-1)+(r+1)(s_0(r)-s_0(l-1))-\sum\limits_{i=l}^rd_ii\\ =&(r+1)s_0(r)-ls_0(l-1)-\sum\limits_{i=l}^rd_ii \end{aligned} \]那么现在可以再用一个树状数组维护 \(s_1(x)=\sum\limits_{i=1}^xd_ii\)。
那么区间和就 \(=(r+1)s_0(r)-ls_0(l-1)-s_1(r)+s_1(l-1)\)。
如何更新：
将 \([l,r]\) 加 \(v\) 的时候，即将 \(d_l\) 加 \(v\)，\(d_{r+1}\) 减 \(v\)。
那么可以将第一个树状数组 \(l\) 位置 \(+v\)，第二个 \(l\) 位置 \(+lv\)；第一个树状数组 \(r+1\) 位置 \(-v\)，第二个 \(r+1\) 位置 \(-(r+1)v\)。
其实本质是树状数组维护 \(k\) 阶前缀和。
开 \(k\) 个树状数组可以做到 \(O(k\log n)\) 维护单点修改和查询 \(k\) 阶前缀和。
标签：rd,limits,树状,线段,ii,数组,卡常,sum From： https://www.cnblogs.com/0x3b800001/p/Fenwick-tree.html