差分题目总和
二维差分
二维差分应用题目：矩形区域加值
题目描述
给定一个大小为 n × n n \times n n×n 的二维矩阵，初始时矩阵中的所有元素都为 0。你需要进行 m m m 次操作，每次操作向某一个矩形区域内的所有元素加上一个固定的值。请你在所有操作完成后输出最终的矩阵。
输入格式
- 第一行包含两个正整数 n n n 和 m m m，表示矩阵的大小和操作的次数。
- 接下来 m m m 行，每行包含五个整数 x 1 , y 1 , x 2 , y 2 , c x_1, y_1, x_2, y_2, c x1,y1,x2,y2,c，表示向以 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 为左上角、 ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 为右下角的矩形区域内的所有元素加上值 c c c。
输出格式
输出 n × n n \times n n×n 的矩阵，表示在所有操作完成后每个位置的值。
样例输入
5 3
1 1 3 3 2
2 2 5 5 3
3 1 4 4 1
样例输出
2 2 2 0 0
2 5 5 3 0
3 6 6 4 3
1 4 4 4 3
0 3 3 3 3
数据范围
- 对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1000 1 \leq n \leq 1000 1≤n≤1000， 1 ≤ m ≤ 10000 1 \leq m \leq 10000 1≤m≤10000。
- 1 ≤ x 1 , y 1 , x 2 , y 2 ≤ n 1 \leq x_1, y_1, x_2, y_2 \leq n 1≤x1,y1,x2,y2≤n，保证输入的矩形区域是合法的，即 x 1 ≤ x 2 x_1 \leq x_2 x1≤x2， y 1 ≤ y 2 y_1 \leq y_2 y1≤y2。
- − 1000 ≤ c ≤ 1000 -1000 \leq c \leq 1000 −1000≤c≤1000。
一维差分
一维差分应用题目：区间加值
题目描述
给定一个长度为 n n n 的数组，初始时数组中的所有元素都为 0。你需要进行 m m m 次操作，每次操作会将一个区间内的所有元素加上某个值。请你在所有操作完成后，输出最终的数组。
输入格式
- 第一行包含两个整数 n n n 和 m m m，表示数组的长度和操作的次数。
- 接下来 m m m 行，每行包含三个整数 l , r , c l, r, c l,r,c，表示将数组中从位置 l l l 到位置 r r r 的所有元素加上值 c c c，即 a [ l ] a[l] a[l] 到 a [ r ] a[r] a[r] 加上 c c c。
输出格式
输出一行，包含 n n n 个整数，表示操作完成后数组的最终值。
样例输入
5 3
1 3 2
2 4 3
3 5 1
样例输出
2 5 6 4 1
题目解析
初始时数组为 [0, 0, 0, 0, 0]，每次进行区间加值操作后数组的变化如下：
- 第一次操作：
[1, 3, 2]，将第1到第3个位置加上2，数组变为[2, 2, 2, 0, 0]。 - 第二次操作：
[2, 4, 3]，将第2到第4个位置加上3，数组变为[2, 5, 5, 3, 0]。 - 第三次操作：
[3, 5, 1]，将第3到第5个位置加上1，数组变为[2, 5, 6, 4, 1]。
可以使用一维差分数组来高效解决这个问题。利用差分数组，我们可以将每次的区间加值操作转换为在区间的端点进行增量操作，最终通过累加差分数组来得到结果。
数据范围
- 对于 100 % 100\% 100% 的数据， 1 ≤ n , m ≤ 100000 1 \leq n, m \leq 100000 1≤n,m≤100000， − 1000 ≤ c ≤ 1000 -1000 \leq c \leq 1000 −1000≤c≤1000。