原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:一个具体值
1.2 题目背景、允许、禁止与限制
背景:
* 有一个由 nnn 个数字组成的序列 aaa
* 定义数列前缀和为 Si=Si−1+aiS_i=S_{i-1}+a_iSi =Si−1 +ai
* 定义数列前前缀和为 SSi=SSi−1+SiSS_i=SS_{i-1}+S_iSSi =SSi−1 +Si
允许:有两种操作
* 一种是“修改”:在 iii 位置把 aia_iai 改成 xxx(同时 SiS_iSi 和 SSiSS_iSSi 也要同步修改)
* 一种是查询:查询 iii 位置上的 SSiSS_iSSi
禁止:
限制:
1.3 题目数据范围与猜测
1≤n,m≤105⟶O(n log n)1 \le n,m \le 10^5 \longrightarrow O(n~log~n)1≤n,m≤105⟶O(n log n)
1.4 一句话概括题意
有一个序列,定义了一个“前缀和”和“前前缀和”,有两种操作,对于每次查询输出具体结果
2 题目破题推导
2.1 第一步:数学
2.1.1普通前缀和:
原数组:a1=1, a2=2, a3=3, a4=4, a5=5a_1=1,\ a_2=2,\ a_3=3,\ a_4=4,\ a_5=5a1 =1, a2 =2, a3 =3, a4 =4, a5 =5
SiS_iSi 的意思:前 iii 个 aaa 全部加起来
* S1=a1=1S_1 = a_1 = 1S1 =a1 =1
* S2=a1+a2=1+2=3S_2 = a_1 + a_2 = 1 + 2 = 3S2 =a1 +a2 =1+2=3
* S3=a1+a2+a3=1+2+3=6S_3 = a_1 + a_2 + a_3 = 1 + 2 + 3 = 6S3 =a1 +a2 +a3 =1+2+3=6
* S4=a1+a2+a3+a4=1+2+3+4=10S_4 = a_1 + a_2 + a_3 + a_4 = 1 + 2 + 3 + 4 = 10S4 =a1 +a2 +a3 +a4 =1+2+3+4=10
* S5=a1+a2+a3+a4+a5=1+2+3+4+5=15S_5 = a_1 + a_2 + a_3 + a_4 + a_5 = 1 + 2 + 3 + 4 + 5 = 15S5 =a1 +a2 +a3 +a4 +a5 =1+2+3+4+5=15
2.1.2 前前缀和:
现在把上面算出来的 S1、S2、S3、S4、S5S_1、S_2、S_3、S_4、S_5S1 、S2 、S3 、S4 、S5 当成新数组,再算一遍前缀和,结果就是 SSiSS_iSSi 。
SSi=S1+S2+S3+⋯+SiSS_i = S_1 + S_2 + S_3 + \dots + S_i SSi =S1 +S2 +S3 +⋯+Si
2.1.3 拆分 SSSSSS
我们把 SS5=1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)SS_5 = 1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5)SS5 =1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5) 全部展开,去掉括号:
SS5=1+1+2+1+2+3+1+2+3+4+1+2+3+4+5\begin{aligned} SS_5 &= 1 \\ &+ 1 + 2 \\ &+ 1 + 2 + 3 \\ &+ 1 + 2 + 3 + 4 \\ &+ 1 + 2 + 3 + 4 + 5 \end{aligned} SS5 =1+1+2+1+2+3+1+2+3+4+1+2+3+4+5
现在数每个数字出现几次:
* 数字 111(a1a_1a1 ):一共出现 555 次
* 数字 222(a2a_2a2 ):一共出现 444 次
* 数字 333(a3a_3a3 ):一共出现 333 次
* 数字 444(a4a_4a4 ):一共出现 222 次
* 数字 555(a5a_5a5 ):一共出现 111 次
规律:
求 SSiSS_iSSi 的时候,第 kkk 个数字 aka_kak ,会出现 (i−k+1)(i - k + 1)(i−k+1) 次。
2.1.4 整理公式
根据前面找到的规律,第 kkk 个数字 aka_kak 在 SSiSS_iSSi 里要乘 (i−k+1)(i-k+1)(i−k+1),所以整体式子是:
SSi=a1×(i−1+1)+a2×(i−2+1)+⋯+ai×(i−i+1)=a1×i+a2×(i−1)+⋯+ai×1\begin{aligned} SS_i &= a_1 \times (i - 1 + 1) + a_2 \times (i - 2 + 1) + \dots + a_i \times (i - i + 1) \\ &= a_1 \times i + a_2 \times (i - 1) + \dots + a_i \times 1 \end{aligned} SSi =a1 ×(i−1+1)+a2 ×(i−2+1)+⋯+ai ×(i−i+1)=a1 ×i+a2
×(i−1)+⋯+ai ×1
第一步:单独拿出任意一项 AK×(I−K+1)A_K \TIMES (I-K+1)AK ×(I−K+1),拆分括号
我们只看其中任意一个小项:ak×(i−k+1)a_k \times (i - k + 1)ak ×(i−k+1)
先调整括号里数字的顺序,重新分组:
i−k+1=(i+1)−ki - k + 1 = (i + 1) - k i−k+1=(i+1)−k
把变形后的括号代回原式:
ak×[(i+1)−k]a_k \times \big[(i+1) - k\big] ak ×[(i+1)−k]
用乘法分配律,把 aka_kak 分别乘进括号里的两个数:
ak×(i+1)−ak×ka_k \times (i+1) - a_k \times k ak ×(i+1)−ak ×k
于是得到单项变形公式:
ak×(i−k+1)=ak×(i+1)−ak×ka_k \times (i - k + 1) = a_k \times (i + 1) - a_k \times k ak ×(i−k+1)=ak ×(i+1)−ak ×k
第二步:把 K=1K=1K=1 到 K=IK=IK=I 的所有项全部代入求和
SSiSS_iSSi 是 kkk 从1加到 iii 的所有单项相加,写成求和符号:
SSi=∑k=1iak×(i−k****S_i = \sum_{k=1}^i a_k \times (i - k + 1) SSi =k=1∑i ak ×(i−k+1)
把上面变形好的单项替换进去:
SSi=∑k=1i[ak×(i+1)−ak×k]SS_i = \sum_{k=1}^i \Big[ a_k \times (i+1) - a_k \times k \Big] SSi =k=1∑i [ak ×(i+1)−ak ×k]
求和可以拆开,变成两个求和式子相减:
SSi=∑k=1iak×(i+1)−∑k=1iak×kSS_i = \sum_{k=1}^i a_k \times (i+1) \quad-\quad \sum_{k=1}^i a_k \times k SSi =k=1∑i ak ×(i+1)−k=1∑i ak ×k
第三步:把常数 (I+1)(I+1)(I+1) 提到求和符号外面
(i+1)(i+1)(i+1) 只和查询的下标 iii 有关,和循环变量 kkk 没有关系,每一项都有这个数,可以直接提取出来:
∑k=1iak×(i+1)=(i+1)×∑k=1iak\sum_{k=1}^i a_k \times (i+1) = (i+1) \times \sum_{k=1}^i a_k k=1∑i ak ×(i+1)=(i+1)×k=1∑i ak
第四步:合并得到最终计算公式
把提取常数后的式子代回去:
SSi=(i+1)×∑k=1iak − ∑k=1i(ak×k)SS_i = (i + 1) \times \sum_{k=1}^i a_k \;-\; \sum_{k=1}^i \big(a_k \times k\big) SSi =(i+1)×k=1∑i ak −k=1∑i (ak ×k)
去掉求和符号,写成直观展开形式:
SSi=(i+1)×(a1+a2+⋯+ai)−(a1×1+a2×2+⋯+ai×i)SS_i = (i + 1) \times \big(a_1 + a_2 + \dots + a_i\big) - \big(a_1 \times 1 + a_2 \times 2 + \dots + a_i \times i\big) SSi =(i+1)×(a1 +a2 +⋯+ai )−(a1 ×1+a2 ×2+⋯+ai ×i)
3 模型匹配
关键词:单点修改,区间修改,单点查询 ⟶\longrightarrow⟶ 树状数组\huge{树状数组}树状数组
3.1 ※重点※
既然我们已经推出了:
SSi=(i+1)×(a1+a2+⋯+ai)−(a1×1+a2×2+⋯+ai×i)SS_i = (i + 1) \times \big(a_1 + a_2 + \dots + a_i\big) - \big(a_1 \times 1 + a_2 \times 2 + \dots + a_i \times i\big) SSi =(i+1)×(a1 +a2 +⋯+ai )−(a1 ×1+a2 ×2+⋯+ai ×i)
我们就可以维护两个树状数组
一个负责求 (a1+a2+⋯+ai)\big(a_1 + a_2 + \dots + a_i\big)(a1 +a2 +⋯+ai ),一个负责求 (a1×1+a2×2+⋯+ai×i)\big(a_1 \times 1 + a_2 \times 2 + \dots + a_i \times i\big)(a1 ×1+a2 ×2+⋯+ai ×i)
因为 i+1i+1i+1 是固定的,加减乘除顺序也是固定的,因此这样没问题
* 如何做到单点“修改”
树状数组解决的是单点增加,那么只需要把修改变成增量就行了
x←a=x←x+(a−x)x\leftarrow a=x\leftarrow x+(a-x) x←a=x←x+(a−x)
4 最终代码(禁止抄袭,仅用于参考)