前缀和和差分可以优化使用枚举解决的区间问题
对比着看
前缀和 差分 作用 快速查询某一区间 快速修改某一区间 相同 原数组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
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
创作不易,做的不好勿喷
发布内容合集