树状数组区间加区间和。
先把区间加进行差分。
区间和：
\[\sum_{i = 1}^{x}\sum_{j = 1}^ic_j = \sum_{i = 1}^{x}(c_i\cdot(x - i + 1)) = (x + 1)\sum c_i - \sum(i\cdot c_i)
\]
所以只需要维护 \(\sum c_i\) 和 \(\sum (i\cdot c_i)\) 即可。
若 \(x\in [1, 2^k]\) 且 \(x\) 随机。
则树状数组区间求和的期望复杂度？
注意到我们每次 -=lowbit(x) 的次数是 \(\operatorname{popcount}(x)\) 的。
所以期望是
\[\dfrac{\operatorname{popcount}(2^k) + \displaystyle\sum_{i = 0}^{2^k - 1}\operatorname{popcount}(x)}{2^k}
\]
对于每个 \(i\)，我们有一个 \(2^k - 1 - i\) 与其配对，使得一共有 \(k\) 个 \(1\)。
所以期望就是
\[E_{query} = \dfrac{1 + k2^{k - 1}}{2^k} = \dfrac{1}{2^k} + \dfrac{k}{2}
\]
对于单点加的复杂度，因为我们每次访问到最高节点后还要再 +=lowbit(x) 一遍，所以期望就是
\[E_{modify} = E_{query} + 1
\]