本文共 589 字，大约阅读时间需要 1 分钟。

前缀和

一维前缀和

例如数列a={2，3，4，7，9},则对应的前缀和数列为sum={2，5，9，16，25}

sum[i]=sum[i-1]+a[i]//其实就是记入累加的和

应用

求第L个数到第R个数的和。

二维前缀和

假设一个矩阵

则该矩阵的二维前缀和为

易得

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

应用

懂得懂得

差分

一维差分（即一维前缀和的逆过程）

例如数列a={（0），1，2，3，3，3，3}，则对应的差分数列d={1，1，1，0，0，0}

d[i]=a[i]-a[i-1];

应用

多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一个的数。例如：使[l,r]每个数加上k，即d[l]–>d[l]+k，d[r+1]–>d[r+1]-k,最后再对a[l,r]做一次前缀和。

例如数列 a={1,2,3,3,3,3},对应的差分数列d={1,1,1,0,0,0}。给数列a的[3,5]加上1，a={1,2,4,4,4,3},对应的差分数列d={1,1,2,0,0,-1}, 相较于原差分序列只改变了端点d[l],d[r+1]。有效地降低了时间复杂度。

二维差分

转载地址：https://blog.csdn.net/YYDS777/article/details/113850645 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！