建设一个用教育网站,顺的品牌网站设计价位,网址交易网站,品牌设计帮文章目录 差分概述题目描述解题思路实现代码 差分概述
在我的博文 算法刷题笔记 前缀和和 算法刷题笔记 子矩阵的和 中#xff0c;曾介绍了前缀和算法。前缀和是指对于一个原始数组#xff0c;我们构建一个含有相同元素个数的辅助数组#xff0c;其中辅助数组的下标为i的元… 文章目录 差分概述题目描述解题思路实现代码 差分概述
在我的博文 算法刷题笔记 前缀和和 算法刷题笔记 子矩阵的和 中曾介绍了前缀和算法。前缀和是指对于一个原始数组我们构建一个含有相同元素个数的辅助数组其中辅助数组的下标为i的元素是原始数组中下标为零的元素一直到下标为i的元素的求和结果。差分算法可以认为是前缀和算法的逆运算。对于原始数组同样构造一个和该数组元素个数相同的辅助数组其中辅助数组的第一个元素和原始数组相同之后辅助数组中下标为i的元素即为原始数组中下标为i的元素和下标为i-1的元素的差。这样将辅助数组中的前i项相加后得到的结果即为原始数组中的第i项元素。差分的主要应用场景为当需要多次对一个数组中不同段的元素都加上一个数时直接使用原始数组的运算时间复杂度会更高而使用差分数组的运算复杂度会更低。
题目描述
输入一个长度为n的整数序列。接下来输入m个操作每个操作包含三个整数l,r,c表示将序列中[l,r]之间的每个数加上c。请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。第二行包含n个整数表示整数序列。接下来m行每行包含三个整数lrc表示一个操作。
输出格式
共一行包含n个整数表示最终序列。
数据范围
1 ≤ n,m ≤ 100000,1 ≤ l ≤ r ≤ n,−1000 ≤ c ≤ 1000,−1000 ≤ 整数序列中元素的值 ≤ 1000
解题思路
第一步数据输入。首先获取用户输入的n和m并存储原始数组。考虑到执行效率选用C语言中效率更高的scanf函数输入而非C中的cin输入由于数组的大小不会超过100000因此构建一个大小为100010的静态数组大10个单元防止越界。第二步构建差分数组。按照差分数组的定义构建差分数组即可。第三步执行区间加法。为了将原始数组内某个区间内的所有元素都增加一个值只需要将辅助数组中区间左端点增加该值然后在右端点删除该值即可。第四步结果输出。通过迭代求和输出最终处理完成的原始数组。
实现代码
#include cstdioconst int N(1e5 10);
int arr[N];
int dif_arr[N];int main(void)
{//原始数组输入部分int n, m;scanf(%d %d, n, m);int x;for(int i(0); i n; i) scanf(%d, arr[i]);//差分数组构造部分dif_arr[0] arr[0];for(int i(1); i n; i) dif_arr[i] arr[i] - arr[i-1];//操作输入部分int l, r, c;for(int i(0); i m; i) {scanf(%d %d %d, l, r, c);dif_arr[l - 1] c;dif_arr[r] - c;}//结果输出部分int sum 0;for(int i(0); i n; i) {sum dif_arr[i];printf(%d , sum);}return 0;
}
