题目:区间加,区间求和。类似线段树1。
众所周知的做法:
设 b 为差分数组。则序列 a 的前缀和 a[1∼x] 整体增加的值就是
∑i=1x∑j=1ib[j]
=∑i=1x(x−i+1)×b[i]
=(x+1)∑i=1xb[i]−∑i=1xi×b[i]
然后用两个树状数组维护即可。其中第一个(称为 c0)维护 b[i] 的前缀和,第二个(称为 c1)维护 i×b[i] 的前缀和。
然后修改时,读入 l,r,k 。
我们需要做的操作是:
- 将树状数组 c0 l 位置加 d,r+1 位置减 d。
- 将树状数组 c1 l 位置加 l×d,r+1 位置减 (r+1)×d。
写到这提醒一下,非讨论区题解,而是为描述问题所需。且解决问题后马上紫衫。
以上,便能解决这道题。
问题是:
显然,我们那样修改 c1 ,然后询问它的前缀和,得出的答案并不是利用暴力把 i×b[i] 求出来的结果。
但是,最后用那个式子计算出的结果却是正确答案,这是为什么?