1.前缀和
求前缀和的时间复杂度与数据的规模有关,但是用前缀和去求某一区间的和时间复杂度为O(1)
一维:
-
一般让下标从1开始,可以避免特判
-
一维前缀和
s[i]=a[1]+a[2]+……+a[i]
-
求数组
[l,r]
之间的和=s[r]-s[l-1]
二维:
- 二维前缀和
s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1]
- 求
[x1,y1]
到[x2,y2]
的和=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]
2.差分
给出一串数a[n]
,构造差分b[n]
, 使得a[i]=b[1]+b[2]+……+a[i]
,可以将差分看作前缀和的逆运算
一维
这样当我们需要给a
数组中的区间[l,r]
都加上c
,只需要将b[l]+c
、b[r+1]-c
,时间复杂度为O(1)
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
二维:
类似于一维,如果要将[x1,y1]
到[x2,y2]
区间中的数都加上c
,只需要将b[x1,y1]+=c
、b[x2+1,y1]-=c
、b[x1,y2+1]-=c
、b[x2-1,y2-1]+=c
参考二维前缀和
原文链接: https://www.cnblogs.com/mpmp/p/17063316.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/313334
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!