先看这题的解法
树状数组维护区间加减区间求和的板子
设原前缀和数组是 $sum[i]$
一个树状数组 $c_0$ 维护与上一道题一样的数组 $b[i]$ ,另一个树状数组 $c_1$ 维护 $b[i] * i$
那么修改后第x个数的前缀和就是 $$sum[x] + (x - 1) * \sum_{i = 1}^xb[i] - \sum_{i = 1}^xb[i] * i$$
即$$sum[x] + (x - 1) * ask(c_0,x) - ask(c_1,x)$$
证明:
修改后第 $x$ 个数的前缀和增加了
$$
\sum_{i = 1}^x\sum_{j = 1} ^ i b[j]$$
$$= \sum_{i=1}^x(x - i + 1) * b[i] $$
$$= (x + 1)\sum_{i = 1}^xb[i] - \sum_{i=1}^xi *b[i]$$
证毕
我曾有过的问题
维护第二个树状数组时,出现了一个令人困惑的点:
假设有一个操作C l r d
,在维护第二个树状数组时只需要把位置 $l$ 上的数加上 $l *d$,位置 $r + 1$ 上的数减去 $(r + 1) * d$ 就可以了。
当时我无法理解这样做的原因
但是我终于悟了
因为 $c_1$ ,它根本就不是一个差分数组。
每次区间修改时,$b[i]$ 数组中只有 $b[l]$ 和 $b[r + 1]$ 发生改变,变化量分别为 $+d$, $-d$
故 $b[i] * i$ 数组中也只有 $b[l] * l$ 和 $b[r + 1] * (r + 1)$ 发生了变化,变化量分别为 $d * l$, $-d * (r + 1)$
我们要的,只不过是 $b[i] * i$ 这个数组的前缀和而已
根本就不用在意前后是否抵消嘛!
问题和你一样,但是没看懂你的解释
能否看懂证明?
当然能
应该是维护的两个东西不相干,各自维护各自的吧qwq