信息学竞赛中的差分技巧

信息学竞赛中的差分技巧差分差分与前缀和在算法中往往对应存在，它是一种策略或者是一种技巧。差分在各级别的算法竞赛中几乎没有独立考察的机会，它往往会作为一个技巧与某主要考点配合使用，比如区间求值问题，或树问题等。令b[i]=a[i]−a[i-1]，即相邻两数的差，即是差分。差分数组可以通过前缀和得到原数组。差分和前缀和是逆运算。一维差分对于一个给定的一维数组arr[]，它的一维差分数组d[]中的d[i]表示数组arr[]的第i个元素与第i-1个元素的差。用公式表示为：d[0]=arr[0],i==0；d[i]=arr[i]-arr[i-1],i>=1。一维差分数组d[]的前缀和就是一维数组arr[]。一维差分在区间求值问题上的应用快速将数组arr[]的区间[l,r]加一个值v。设有m次这样的区间操作，每次操作给出l,r和v。要求输出m次操作后的数组arr[]。遍历区间[l,r]中的所有元素并加上一个值v，是最传统的暴力思路。这样的区间操作，每次的时间复杂度为O(n)，要求进行m次，所以时间复杂度为O(m*n)。使用差分可以将在数组arr[]上的区间操作转化为在差分数组d[]上的"单点操作"。即将区间修改，转化为单点修改。转化方式：将数组arr[]的区间[l,r]加一个值v等价于将差分数组中的d[l]+v，d[r+1]-v。差分数组的前缀和相当于原数组，所以给差分数组中的d[l]+v，d[r+1]-v就相当于将数组arr[]的区间[l,r]加一个值v。最终的时间复杂度为O(n+m)。一维差分的局限性一维差分可以将时间复杂度O(n)的区间修改，改为O(1)的端点修改。但是差分数组对于单点查询的效率不够，一次查询arr[i]需要计算d[i]的前缀和，时间复杂度为O(n)。例如长度为n的数列进行m次区间修改，k次单点查询，使用一维差分数组的时间复杂度为O(m+n*k)，使用暴力算法的时间复杂度为O(m*n+k)。因此区间修改+单点查询的问题，经常使用差分数组+树状数组/线段树的组合。一维差分模板输入一个长度为n的整数序列。接下来输入m个操作，每个操作包含三个整数l，r，c，表示将序列中[l,r]之间的每个数加上c。请你输出进行完所有操作后的序列。输入第一行包括两个整数n和m。第二行包括n个整数，表示整数序列。接下来m行，每行包括三个整数l，r，c，表示一个操作。输出共一行，包含n个整数，表示最终序列。输入样例：输出样例：63345342122121021241051二维差分一个给定的二维数组arr[]，它的二维差分数组d[]中d[i][j]可以用如下公式计算：d[0][0]=arr[0][0],i,j==0；d[0][j]=arr[0][j]-arr[0][j-1],i==0,j>=1；d[i][0]=arr[i][0]-arr[i-1][0],i>=1,j==0；d[i][j]=arr[i][j]-arr[i-1][j]-arr[i][j-1]+arr[i-1][j-1],i,j>=1二维差分应用二维差分的主要用处是快速地将一个区块中的所有元素都加上一个值v。使用差分可以将在数组arr[]上的区块操作转化为在差分数组d[]上的单点操作。差分矩阵模板输入一个n行m列的整数矩阵，再输入q个操作。每个操作包含五个整数x1,y1,x2,y2,c，其中(x1,y1)和(x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上c。请你将进行完所有操作后的矩阵输出。输入第一行包含整数n,m,q。接下来n行，每行包含m个整数，表示整数矩阵。接下来q行，每行包含5个整数x1,y1,x2,y2,c，表示一个操作。输出共n行，每行m个整数，表示所有操作进行完毕后的最终矩阵。输入样例：输出样例：343234112214341322122221111001110212220231代码略。有兴趣的朋友可以在网站留言区讨论代码，谢谢。三维差分元素值用三维数组arr[][][]来定义，差分数组d[][][]也是三维的。与之前低维度的差分类似，把三维差分想象成立体空间的操作。与之对应的小立方块有8个顶点，所以三维的区间需要修改8个d[][][]的值。在二维差分中，arr[][]是差分数组d[][]的前缀和，即原点坐标(1，1)和坐标(i，j)围成的矩阵面积。在三维差分中，arr[][][]是差分数组d[][][]的前缀和，即原点坐标(1,1,1)和坐标(i,j,k)围成的立体体积。把每个d[][][]看成一个小立方体，在坐标(1，1，1)~(i，j，k)所围成的空间中，所有小立体加起来的总体积即为arr[i][j][k]。在三维情况下，差分就变成了相邻的arr[][][]的体积差。三维的差分数组d[][][]，其递推式如下：d[i][j][k]=s[i][j][k]−s[i−1][j][k]−s[i][j−1][k]−s[i][j][k−1]+s[i−1][j−1][k]+s[i−1][j][k−1]+s[i][j−1][k−1]−s[i−1][j−1][k−1]差分数组应用：三体攻击三体人将对地球发起攻击。为了抵御攻击，地球人派出了A*B*C艘战舰，在太空中排成一个A层B行C列的立方体。其中第i层第j行第k列的战舰（记为战舰(i,j,k)）的生命值为d(i,j,k)。三体人将会对地球发起m轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第t轮攻击用7个参数lat,rat,lbt,rbt,lct,rct,ht描述；所有满足i∈[lat,rat],j∈[lbt,rbt],k∈[lct,rct]的战舰(i,j,k)会受到ht的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。输入第一行包括4个正整数A,B,C,m；第二行包含A*B*C个整数，其中第((i−1)*B+(j−1))*C+(k−1)+1个数为d(i, j, k)；第3到第m+2行中，第(t−2)行包含7个正整数lat, rat, lbt, rbt, lct, rct, ht。输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。数据范围：1≤A*B*C≤10^6,1≤m≤10^6,0≤d(i, j, k), ht≤10^9,1≤lat≤rat≤A,1≤lbt≤rbt≤B,1≤lct≤rct≤C，层、行、列的编号都从1开始。输入样例：输出样例：2223211111111121211111121211111112此题为典型的区间修改、查询题目，且区间为三维。某一维的数据范围在10^6，用暴力会导致直接超时。使用差分修改，在O(1)的时间复杂度，代替暴力O(n^2)修改，会好一些