差分:修订间差异

来自吾萌百科
(创建页面,内容为“对于一个给定的数列A,它的差分数列B定义为: <math> B_i=\begin{cases} A_1 &i=1 \\ A_i-A_{i-1}&i>1 \end{cases} </math>”)
 
无编辑摘要
第6行: 第6行:
\end{cases}
\end{cases}
</math>
</math>
把数列A的区间[l,r]加d,其差分数列B的变化为
# <math>B_l=B_l+d</math>
# <math>B_{r+1}=B_{r+1}-d</math>
这样可以使得我们把原数列上的“区间操作”转化为差分数列上的“单点操作”进行计算,降低求解难度。
== 参考资料 ==
# 算法竞赛进阶指南,李煜东,23页
[[Category:计算机]]

2022年2月20日 (日) 16:49的版本

对于一个给定的数列A,它的差分数列B定义为: [math]\displaystyle{ B_i=\begin{cases} A_1 &i=1 \\ A_i-A_{i-1}&i\gt 1 \end{cases} }[/math]

把数列A的区间[l,r]加d,其差分数列B的变化为

  1. [math]\displaystyle{ B_l=B_l+d }[/math]
  2. [math]\displaystyle{ B_{r+1}=B_{r+1}-d }[/math]

这样可以使得我们把原数列上的“区间操作”转化为差分数列上的“单点操作”进行计算,降低求解难度。

参考资料

  1. 算法竞赛进阶指南,李煜东,23页