差分
已知前缀和 S[n], 构造 b[n]
满足条件: S[i] = b1 + b2 + … + b[n]
差分就是前缀和的逆运算
构造 b[n]
理解即可, 没有那么重要, 通过插入操作构造 b[n]
b[1] = a[1]
b[2] = a[2] - a[1]
b[3 ]= a[3] - a[2]
...
b[n] = a[n] - a[n-1]
-
b[n]称为 S[n]的差分
-
S[n]称为 b[n]的前缀和
差分的用途
对 S数组的某个区间内的数全部加上 c, 现在只需要对 b数组的 2 / 4个数加上 c
时间复杂度由 O(n) -> O(1)
一维数组差分
假设已经求出来 b数组, 只要对 b数组求前缀和就可以求出原数组 S[n]
已知 b[n], 可以用 O(n) 的时间得到 S[n]
差分帮助我们处理一种操作, 在 S数组的 [l, r]区间内加上数 c. 则
1. a[l] ~ a[L-1]无影响
2. a[l] ~ a[r] 加上了 c
3. a[r=1] ~ a[n] 无影响
S数组操作后 对于 b数组的影响, 相当于 b[l] + c, b[r + 1] - c
题目 797
如果使用 Scanner输入和 Systemout.println(), 会报输出错误, 要使用 BufferReader和BufferReader
代码
import java.io.*;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = 100010; // 数据规模为 10w
static int[] b = new int[N]; // b数组为 arr数组的差分
static int[] arr = new int[N]; // arr数组为 b数组的前缀和
// 对差分数组进行插入操作
private static void insert(int l, int r, int val) {
// 可以画图进行理解
b[l] += val;
b[r + 1] -= val;
}
// 程序入口
public static void main(String[] args) throws IOException {
// 初始化输入数据
String[] s = reader.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
String[] sArr = reader.readLine().split(" ");
for (int i = 1; i <= n; i++) // 注意下标为 1
arr[i] = Integer.parseInt(sArr[i - 1]);
// 初始化 b数组
for (int i = 1; i <= n; i++) {
// 相当于将 arr中全部看为 0, 则 b[n]中也全部都为 0, 再在其中区间 [i, i] 添加 arr[i], 求出 b[i]
insert(i, i, arr[i]);
}
// m次循环操作
while (m-- > 0) {
String[] sIn = reader.readLine().split(" ");
int l = Integer.parseInt(sIn[0]), r = Integer.parseInt(sIn[1]), val = Integer.parseInt(sIn[2]);
insert(l, r, val);
}
// 求数组 arr插入元素后的值, 相当于求 b[n]的前缀和
for (int i = 1; i <= n; i++) {
arr[i] = arr[i - 1] + b[i];
log.write(arr[i] + " ");
}
// 释放资源
reader.close();
log.flush();
log.close();
}
}
这个是将c++排名第一的解析和上面的答案结合了一下,希望能给你帮助
### This summary is great!
有个typo 但还是总结的很好谢谢!