关于树状数组
  • 板块学术版
  • 楼主over_caykl
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/6/16 23:20
  • 上次更新2023/10/23 13:00:07
查看原帖
关于树状数组
271803
over_caykl楼主2023/6/16 23:20

题目:区间加,区间求和。类似线段树1。


众所周知的做法:

设 bb 为差分数组。则序列 aa 的前缀和 a[1∼x]a[1\sim x] 整体增加的值就是

∑i=1x∑j=1ib[j]\sum_{i=1}^x \sum_{j=1}^i b[j]

=∑i=1x(x−i+1)×b[i]=\sum_{i=1}^x(x-i+1)\times b[i]

=(x+1)∑i=1xb[i]−∑i=1xi×b[i]=(x+1)\sum_{i=1}^x b[i]-\sum_{i=1}^x i \times b[i]

然后用两个树状数组维护即可。其中第一个(称为 c0c_0)维护 b[i]b[i] 的前缀和,第二个(称为 c1c_1)维护 i×b[i]i \times b[i] 的前缀和。

然后修改时,读入 l,r,kl,r,k 。
我们需要做的操作是:

  1. 将树状数组 c0c_0 ll 位置加 dd,r+1r+1 位置减 dd。
  2. 将树状数组 c1c_1 ll 位置加 l×dl \times d,r+1r+1 位置减 (r+1)×d(r+1) \times d。

写到这提醒一下,非讨论区题解,而是为描述问题所需。且解决问题后马上紫衫。

以上,便能解决这道题。

问题是:

显然,我们那样修改 c1c_1 ,然后询问它的前缀和,得出的答案并不是利用暴力把 i×b[i]i \times b[i] 求出来的结果。
但是,最后用那个式子计算出的结果却是正确答案,这是为什么?

2023/6/16 23:20
加载中...