前缀和 差分 C++ 小结

简介: 前缀和 差分 C++ 小结

·差分和前缀和互为逆运算

·合理地使用前缀和和差分能使得复杂问题简单化

前缀和:

一维

~预处理(递推关系)s[i]=s[i-1]+a[i]

查询(O(1)) L到R的区间和 S = s[R]-s[L-1]

二维

s[i][j]代表左上角(1,1)到左下角(i,j)围成的矩阵的元素和


20201214201734653.png

至于为什么是(1,1)而不是(0,0),主要是为了使得在递推的时候,避免下标出现负数的情况;


预处理(递推关系):


s[i][j] = s[i-1][j]+(s[i][j-1]-s[i-1][j-1])+a[i][j]    (i,j>=1)


而当i或j等于 = 0的时候,初始化等于0(就是说输入数据的时候行列都从1开始)


而当i或j等于1的时候,递推关系依旧成立(此时就是一维的递推关系)


查询:


时间复杂度O(1)


以(x1,y1)为左上角 (x2,y2)为右下角围成的矩形的元素和(设为F)


F = s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1] (脑海里想一下排列着的数字就容易出来了)


差分

一维:已知数列an,a0=0;

构造差分数列 bn = an-an-1

累加法

b1=a1-a0

b2=a2-a1

....

bn=an-an-1,累加得到b1+b2..bn=an-a0=an ,即an是bn的前缀和


问题:给定n个数,如何将第l个数字到第r个数字都加上c


循环可,下面介绍差分


设这n个数构成一段前缀和序列an


构造对应于an的差分序列bn,(b1=a1);那么有an=b1+b2+..bn


b1,b2,b3,.....bl...br,br+1..bn


我们对第bl的数字加上c,对第r+1个数字减掉c,设cn是对应于此时序列的前缀和序列


c1,c2...cl...cr,cr+1...cn可以表示为


b1,   b1+b2 ...b1+b2+...bl+c.....b1+b2+..(bl+c)+...br,.b1+b2+..(bl+c)+...br+(br+1-c)....


可以看到第1至l-1个数 cn=an


而第l至第r个数 cn=an+c


而第r+1至第n个数 cn = an ,那么可以发现,此时的前缀和序列cn,正是我们想要达到的效果;


二维


已知二维数组a[i][j]代表左上角(1,1)到右下角(i,j)所围成的矩形的元素和。


构造差分数列b[i][j]


b[i][j] = a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1] (脑海里想着几排数字就可以出来了)


问题:给定n个数放入二位数字a[i][j]中,如何将以(x1,y1)为左上角 (x2,y2)为右下角所围成矩形的所有元素加上c


思路和一维类似,通过对差分数列的加加减减,最后通过这个处理过的差分数列得到一个新的前缀和序列即所求的问题答案


这里感觉理解起来还是有点麻烦,虽然还是能弄出来,就先粗糙的理解吧:


对左上角的元素(x1,y1),加上c,然后对于右上角(x1,y2+1)-c,


然后对于左下角(x2+1,y1)-c,由于减了两次,然后对右下角(x2+1,y2+1)-c(非常粗糙,后续再加强理解吧)


反正二维差分对一个矩形内的元素加减,只需要对四个边角差分元素加加减减,最后得到一个新的二维前缀和序列即可。


奔赴热爱 奔赴山海 算法 数学 永不凋谢。


相关文章
|
7月前
|
算法 测试技术 C++
【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠
【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠
|
2月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
2月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
7月前
|
算法 C++
c++算法学习笔记 (5)前缀和+差分
c++算法学习笔记 (5)前缀和+差分
|
7月前
|
算法 测试技术 C#
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
|
7月前
|
算法 测试技术 C#
C++前缀和算法:统计美丽子字符串
C++前缀和算法:统计美丽子字符串
|
算法 测试技术 C#
C++前缀和算法的应用:最大化城市的最小供电站数目(二)
C++前缀和算法的应用:最大化城市的最小供电站数目
|
算法 测试技术 C++
C++前缀和算法的应用:最大化城市的最小供电站数目(一)
C++前缀和算法的应用:最大化城市的最小供电站数目
|
7月前
|
算法 测试技术 C++
C++前缀和算法:统计美丽子字符串
C++前缀和算法:统计美丽子字符串
|
14天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
25 2