【题目来源】
AcWing：797. 差分 - AcWing题库
【题目描述】
输入一个长度为 \(n\) 的整数序列。
接下来输入 \(m\) 个操作，每个操作包含三个整数 \(l,r,c\)，表示将序列中 \([l,r]\) 之间的每个数加上 \(c\)。
请你输出进行完所有操作后的序列。
【输入】
第一行包含两个整数 \(n\) 和 \(m\)。
第二行包含 \(n\) 个整数，表示整数序列。
接下来 \(m\) 行，每行包含三个整数 \(l,r,c\)，表示一个操作。
【输出】
共一行，包含 \(n\) 个整数，表示最终序列。
【输入样例】
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
【输出样例】
3 4 5 3 4 2
【解题思路】
【算法标签】
《AcWing 797 差分》 #差分#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100010; // 定义数组最大长度int n, m; // n: 数组长度, m: 操作次数
int a[N]; // 原始数组
int b[N]; // 差分数组/*** 差分数组区间更新操作* @param l 区间左端点* @param r 区间右端点* @param c 要增加的值*/
void insert(int l, int r, int c)
{b[l] += c; // 左端点加cb[r + 1] -= c; // 右端点+1位置减c
}int main()
{// 输入数组长度和操作次数scanf("%d%d", &n, &m);// 输入原始数组for (int i = 1; i <= n; i++){scanf("%d", &a[i]);}// 初始化差分数组（两种方式等价）// 方式1: 直接计算差分 b[i] = a[i] - a[i-1]// 方式2: 通过insert函数逐个元素插入for (int i = 1; i <= n; i++){insert(i, i, a[i]);}// 处理每个区间更新操作while (m--){int l, r, c;scanf("%d%d%d", &l, &r, &c);insert(l, r, c); // 执行区间更新}// 计算前缀和，得到更新后的数组for (int i = 1; i <= n; i++){b[i] += b[i - 1];}// 输出最终数组for (int i = 1; i <= n; i++){printf("%d ", b[i]);}return 0;
}
【运行结果】
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
3 4 5 3 4 2