算法（二）——一维差分、等差数列差分

文章目录

一维差分、等差数列差分
- 一维差分
- - 例题：航班预订统计
- 等差数列差分
- - 例题：三步必杀
  - 例题：Lycanthropy

一维差分、等差数列差分

一维差分

差分解决的是 区间修改（更新）问题，特别是多次区间修改问题，能将每次修改的复杂度控制到O(1)，解题的一般步骤：

初始化差分数组

对于一个给定的数组 a，其差分数组 d 的定义如下：
1. d[0] = a[0]
2. 对于 i 从 1 到 n−1，d[i]=a[i]−a[i−1]
这样，差分数组 d 的每个元素 d[i] 表示原数组 a 中第 i 个元素与第 i−1 个元素的差值。
确定修改区间并根据修改要求修改差分数组

假设我们要修改的区间是l、r，其中l和r分别是区间的起始位置和结束位置，要修改的操作是：对[l, r]区间内的所有元素加一个数num，修改的操作为：差分数组d[l] += num，d[r + 1] -= num（前提：r + 1 不会越界，不过通常我们可以申请一个较大数组避免越界即可）。
差分数组求前缀和得到修改后的数组

之前区间修改操作都在差分数组中体现，差分数组其实就代表了最终的数组，求解最终数组只需要计算差分数组的前缀和即可，具体：
1. 初始化前缀和数组 s 的第一个元素 s[0] 为差分数组 d 的第一个元素 d[0] ，即 s[0] = d[0]。
2. 对于 i 从 1 到 n−1 ，计算 s[i] = s[i − 1] + d[i]。

举一个例子，假如有一个数组a: [3, 5, 2, 6, 4]，修改操作：

对[1, 3]的元素加5
对[2, 4]的元素减2

初始化差分数组d: [3, 2, -3, 4, -2]
处理第一次修改得：d: [3, 7, -3, 4, -7]
处理第二次修改得：d: [3, 7, -5, 4, -7]
得到最终数组：s: [3, 10, 5, 9, 2]

例题：航班预订统计

原题链接：1109. 航班预订统计 - 力扣（LeetCode）

在这里插入图片描述

这是一道典型的一维差分问题，只是初始数组是一个全零数组，意味着差分数组也是全零的，我们只需要每次O(1)地修改差分数组，最后求前缀和返回即可。

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] ret = new int[n];for(int i = 0; i < bookings.length; i++) {ret[bookings[i][0] - 1] += bookings[i][2];if(bookings[i][1] - 1 < n - 1) {ret[bookings[i][1]] -= bookings[i][2];}}for(int i = 1; i < n; i++) {ret[i] += ret[i - 1];}return ret;}
}

这里只创建了一个数组，通过下标映射将其正确地更新为最终数组

等差数列差分

等差数列差分的问题描述：

原数组全为0，接下来会有多个区间修改操作，每次操作：数组的 l~r 范围上的元素依次加上首项s、尾项e、公差d的等差数列，最终返回多次更新后的结果。

等差数列差分当然也是区间修改问题，题目会给出五个参数（有时没有给出5个参数，但是缺少的参数可以由其他参数得到，例如公差）：

l：修改区间的起始位置
r：修改区间的结束位置
s：等差数列的首项
e：等差数列的尾项
d：等差数列的公差

等差数列差分的做题步骤：

由于原数组全0，因此差分数组实际上也是全0，可以将原数组作为差分数组使用
对于差分数组d[]，执行如下修改：d[l] += s，d[l + 1] += d - s、d[r + 1] -= d + e、d[r + 2] += e
最终对差分数组求两次前缀和得到最终数组

举个例子：现对一个全0数组[0, 0, 0, 0, 0, 0]进行如下修改操作：(结果应该是：[0, 3, 7, 16, -1, -7])

对[1, 3]区间的元素从左往右加上首项为3，尾项为11的等差序列的每一项
对[3, 5]区间的元素从左往右加上首项为5，尾项为-7的等差数列的每一项

第一次修改：d[1] += 3，d[1 + 1] += (4 - 3) ，d[3 + 1] -= (4 + 11)，d[3 + 2] += 11 ，得到d: [0, 3, 1, 0, -15, 11]
第二次修改：d[3] += 5，d[3 + 1] += (-6 - 5) ，d[5 + 1] -= (-6 + (-7))（越界，但是我们可以一开始就选择创建一个较大的数组），d[5 + 2] += (-7) ，得到d: [0, 3, 1, 5, -26, 11]
求两次前缀和：[0, 3, 4, 9, -17, -6]；[0, 3, 7, 16, -1, -7]，第二次前缀和的结果就是最终数组。

简单反向验证一下4步修改（d[l] += s，d[l + 1] += d - s、d[r + 1] -= d + e、d[r + 2] += e ）的公式：

假设原数组：[0, 0, 0, 0, 0, 0, 0, 0]，已知l、r、s、e、d

在这里插入图片描述

第二次前缀和的结果就是最终结果，反推第一次前缀和的结果如图，再次反推四次修改后的结果，可以发现，l位置 += s、l+1位置 += d-s、r+1位置 += (-d-e) <=> r+1位置 -= d+e、r+2位置 += e

例题：三步必杀

原题链接：P4231 三步必杀 - 洛谷 | 计算机科学教育新生态

在这里插入图片描述

很典型的等差数列差分问题，基本没有绕弯子，可以直接用技巧解决，关键是看出能得出5个参数，也很简单不再赘述。

另外，洛谷是ACM模式的，注意上一篇介绍的输入输出的处理。

import java.io.*;//洛谷的主类必须是Main
public class Main {public static int MAX_N = 10_000_005;public static long[] arr = new long[MAX_N];public static int m, n;public static void main(String[] args) throws IOException {try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out))) {StreamTokenizer in = new StreamTokenizer(br);while(in.nextToken() != StreamTokenizer.TT_EOF) {n = (int) in.nval;in.nextToken();m = (int) in.nval;for(int i = 0, l, r, s, e; i < m; i++) {in.nextToken();l = (int) in.nval;in.nextToken();r = (int) in.nval;in.nextToken();s = (int) in.nval;in.nextToken();e = (int) in.nval;set(l, r, s, e, (e - s) / (r - l));}build();long max = arr[1];long ret = arr[1];for(int i = 2; i <= n; i++) {if(arr[i] > max) {max = arr[i];}ret ^= arr[i];}out.println(ret + " " + max);out.flush();}}}//两次前缀和private static void build() {for(int i = 2; i <= n; i++) {arr[i] += arr[i - 1];}for(int i = 2; i <= n; i++) {arr[i] += arr[i - 1];}}//四次修改private static void set(int l, int r, int s, int e, int d) {arr[l] += s;arr[l + 1] += d - s;arr[r + 1] -= d + e;arr[r + 2] += e;}
}

例题：Lycanthropy

原题链接：P5026 Lycanthropy - 洛谷 | 计算机科学教育新生态

在这里插入图片描述

粗略地读题目，可以捕捉到有等差数列以及修改的关键字，并且可以确定全零原数组，因此可以判定这是一道等差数列差分问题。

想象一下，一个物体落水了，落水点周围的水位是不是下降了，再往外水就会溅起来，落水范围由落水点以及方块体积决定，大体状况如下图：

在这里插入图片描述

我们能够观察到四个单调区间（题目描述了6个，但是可以合成为4个），因此每个小方块落水，会对数组进行四个区间修改，处理好边界得出5个参数即可。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.io.BufferedWriter;public class Main {public static int MAX_L = 1_000_001;public static int OFFSET = 30001;public static int[] arr = new int[OFFSET + MAX_L + OFFSET];public static int n, m;public static void main(String[] args) throws IOException {try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)))) {StreamTokenizer in = new StreamTokenizer(br);while(in.nextToken() != StreamTokenizer.TT_EOF) {n = (int) in.nval;in.nextToken();m = (int) in.nval;for(int i = 0, v, x; i < n; i++) {in.nextToken();v = (int) in.nval;in.nextToken();x = (int) in.nval;set(v, x);}build();int start = OFFSET + 1;out.print(arr[start++]);for(int i = 2; i <= m; i++) {out.print(" " + arr[start++]);}out.flush();}}}public static void set(int v, int i) {_set(i - 3 * v + 1, i - 2 * v, 1, v, 1);_set(i + 2 * v + 1, i + 3 * v - 1, v - 1, 1, -1);_set(i - 2 * v + 1, i, v - 1, -v, -1);_set(i + 1, i + 2 * v, -v + 1, v, 1);}public static void _set(int l, int r, int s, int e, int d) {arr[l + OFFSET] += s;arr[l + 1 + OFFSET] += d - s;arr[r + 1 + OFFSET] -= d + e;arr[r + 2 + OFFSET] += e;}public static void build() {for(int i = 1; i <= m + OFFSET; i++) {arr[i] += arr[i - 1];}for(int i = 1; i <= m + OFFSET; i++) {arr[i] += arr[i - 1];}}
}