常用算法讲解--前缀和与差分篇
2025-07-30 10:35:11
发布于:河北
前缀和和差分可以优化使用枚举解决的区间问题
对比着看
前缀和 | 差分 | |
---|---|---|
作用 | 快速查询某一区间 | 快速修改某一区间 |
相同 | 原数组a、前缀和数组s | 原数组a、差分数组f(所有数组名自定义) |
构造 | s的构造(见下) | f的构造(见下) |
之后怎么用 | 查询(见下) | 修改(见下) |
你知道吗 | 是差分的逆运算 | 是前缀和的逆运算 |
时间复杂度 | 构造:O(n)一维数组 | 构造:O(n)一维数组 |
时间复杂度 | 查询:O(1) | 查询:O(1) |
空间复杂度 | O(n)一维数组 | O(n)一维数组 |
特点 | 空间换时间 | 空间换时间 |
前缀和
前缀和的构造
s[1] = a[1]
s[2] = a[1] + a[2]
s[3] = a[1] + a[2] + a[3]
......
s[i]=a[1]+a[2]+......+a[i-1]+a[i]
s[i]=s[i-1]+a[i]
因为s[i - 1]=a[1] + a[2] + ...... + a[i - 1]
前缀和如何查询区间和
[l,r] = s[r] - s[l - 1]
差分
差分的构造
f[1] = a[1]
f[2] = a[2] - a[1]
......
f[i]=a[i] - a[i - 1]
差分如何修改区间
将[l,r]所有数+c
f[l] += c
f[r +1] -= c
推导
还原
因为f是a的差分,a是f的前缀和
所以a[i] = a[i -1] + f[i]
补充
二维前缀和构建
s[i][j]=s[i-1][j]+s[i][j -1]+s[i-1][j-1]+a[i][j]
二维前缀和查询
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
二维差分构建
f[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
二维差分修改区间
f[x1][y1]+=d;
f[x1][y2+1]-=d
f[x2+1][y1]-=d
f[x2+1][y2+1]+=d
创作不易,做的不好勿喷
发布内容合集
全部评论 2
d
19小时前 来自 河北
0d
19小时前 来自 河北
0
有帮助,赞一个