数组差分与前缀和

本文主要是介绍数组差分与前缀和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数组差分与前缀和

一、差分

差分就是把数组表现成初始数和一堆差的形式。
例：7 9 2 1 4 5
差分形式：7 2 -7 -1 3 1
这时可以发现:
\(7=7\)
\(9=7+2\)
\(2=7+2+(-7)\)
\(1=7+2+(-7)+(-1)\)
\(4=7+2+(-7)+(-1)+3\)
\(5=7+2+(-7)+(-1)+3+1\)
当把数组转换成差分形式后，就可以很轻松的进行区间修改
如果想要把\(a[x]-a[y]\)同时加上\(delta\)，只需将\(d[x]+Δ,d[y+1]-Δ\)，这时再

\[\sum\limits_{j = 1}^{n} d_j = a[i] \]

就可以得出修改后的\(a[n]\)了。
差分的优点在于可以通过修改差分数组起始和结尾来迅速进行区间修改。

二、前缀和

前缀和本身与差分差不多。
例：7 9 2 1 4 5
前缀和形式：7 16 18 19 23 28
通过观察，可以发现\(a[i]=d[i+1]-d[i]\)
那么\(d[x]-d[y-1]\)就可以求出\([a[x],a[y]]\)这个区间的和，从而实现区间求和的目的。
前缀和的优点在于可以通过将数组两项做差方便的进行区间求和。

这篇关于数组差分与前缀和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程