主播刚开始学算法时觉得差分和前缀和这两个东西名字很吓人非常的难写。其实它们一点也不吓人。你可以先记住一句话前缀和快速求一段区间的和。差分快速对一段区间整体加减。如果把数组看成一排数字那么前缀和解决的是这一段数字加起来等于多少。差分解决的是这一整段数字都加上一个数怎么做的更快。一.学前缀和和差分的作用先看一个很常见的问题。有一个数组如果我要问你第2个到第4个数和是多少第1个到第5个数和是多少第3个到第5个数和是多少你当然可以每次一遍遍的加但如果题目的数据范围很大呢这时候你如果还是每次都重新加速度就会很慢。所以我们就需要一种方法能让求一段区间和变得特别快这就是前缀和。同理如果题目不是问区间和而是让你把第2个到第4个数都加3。把第1个到第5个数都减2。把第3个到第6个数都加10。如果每次都一个个改也会很慢。所以我们还需要一种方法能让区间整体修改变得很快这就是差分。二、前缀和是什么1前缀和的定义前缀和顾名思义就是前面所有数的和。比如数组a[12345]我们定义一个新数组s其中s[1]表示前1个数的和。s[2]表示前2个数的和。s[3]表示前3个数的和。......那么s[1]1s[2]123s[3]1236s[4]123410s[5]1234515所以前缀和数组就是s[0,1,3,6,10,15]前缀和数组定义时每次多放一位0是为了方便计算。2前缀和怎么求公式很简单意思是前i个数的和前i-1个数的和第i个数。3前缀和最重要的作用快速求区间和比如我们要求第l个到第r个数的和。正常做法是前缀和的做法是4为什么是因为a[r]是前r个数的和。a[l-1]是前l-1个数的和。把前面那一段减掉剩下的就是l到r的和。举一个例子还是a[12345]前缀和s[0,1,3,6,10,15]求第2到第4个数的和s[4]-s[1]10-19而原数组第2到第4个数是2349两个的结果完全一样。三、前缀和模板1一维前缀和模板n len(a) s [0] * (n 1) for i in range(1, n 1): s[i] s[i - 1] a[i - 1]四、差分是什么如果说前缀和是快速求和那么差分就是快速修改。1差分的核心想法假设现在有数组a[1,2,3,4,5]我想把第2到第4个数都加3。改完后直接变成a[1,5,6,7,5]普通做法是第2个加3第3个加3第4个加3这样一个个改。但差分的思想是不直接改整个区间只在区间的开头和结尾做标记。2差分数组的定义差分数组b满足b[i]a[i]-a[i-1]也就是说差分数组记录的是当前数和前一个数差了多少。比如a[1,2,3,4,5]那么差分数组可以是b[1]1b[2]2-1b[3]3-2b[4]4-3b[5]5-4所以b[1,1,1,1,1]3差分怎么进行区间修改如果要把区间[lr]都加上K只需要b[l]kb[r1]-k4为什么这样做是对的因为从l开始后面的数都应该多k。从r1以后这个多出来的k就应该停在。所以在l位置加上k表示从这里开始整体增加。在r1位置减去k表示从这里后面停止增加。这就像在一个区间的左右两打标记一样。5差分数组a[1,2,3,4,5]b[1,1,1,1,1]现在给区间[2,4]加上3。那么只需要b[2]3b[5]-3得到b[1,4,1,1,-2]然后再把差分数组还原成原数组第1个数1第2个数145第三个数516第四个数617第五个数7-25得到[1,5,6,7,5]正好就是我们想要的结果。五、差分模板1建立差分数组import sys from collections import deque,defaultdict inputsys.stdin.readline nlen(a) b[0]*(n2) b[1]a[0] for i in range(2,n1): b[i]a[i-1]-a[i-2]2区间修改把[lr]全部加上k:b[l]k b[r1]-k3还原原数组for i in range(1,n1): b[i]b[i-1]此时b[i]就已经变成修改后的原数组了。六、前缀和和差分的关系这两个东西其实是反过来的关系。前缀和是把原数组不断累加差分是看原数组相邻两项的差值所以可以理解为前缀和往前累加。差分看变化量。七、什么时候用前缀和什么时候用差分这个非常的重要。用前缀和的情况当题目经常问你区间和一段连续数字的总和多次查询某段区间的和这时候优先想到前缀和。用差分的情况当题目经常让你给一整段区间同时加一个数。多次进行区间修改。最后再求整个数组结果这时候优先想到差分。一句话总结多次查询区间和用前缀和。多次修改整个区间用差分。八、常见的错误点1下标混乱2忘记把数组开大一个位置3前缀和公式写错