流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

get--->差分数组

　　作者: 流离之人追逐幻影　　　　发表时间：2019-09-23 23:51:54 浏览：387　|　评论：0　

差分数组主要是用在 “每次操作在Li和Ri这个区间加上一个数Ci“ 具有这种特征的题目，暴力的方法会TLE,线段树写起来又复杂了点，这时候可以考虑使用差分数组来ac。

------------

![](/image_editor_upload/20190923112144_69658.png)
如果使用暴力每次对d[i]累加ci，(假设操作了n次)时间复杂度实际为O(n*(Ri-Li)),最坏情况是O(n^2).

关键：
```
这时候将Li-Ri加Ci, 变成在d[Li]处增加Ci, 在d[Ri+1]处减去Ci.然后使用递推公式f[i]=d[i]+d[i-1].数学原理是裂项相消
如图：
   在0~3加1，  在2~7加3；  变成在d[0]处加 1， d[4]减去 1；在d[2]处加 3，在d[8]处 -3。
   因为d[0]处加的值，根据递推公式会影响包括d[1]往后的值，这时候为了不影响到d[4]就在d[4]处减1;在d[2]处加3同理。这样就完成了对差分数组的构造，现在只需要维护一个差分数组就可以了。询问一个位置的元素值，最坏时间复杂度为O(n)。
```

------------

例题：
```
题目描述 
牛村村口有一排防护塔，建的越高防护范围越广。
牛可乐被村长安排去建塔，他每天的工作是给连续的几个塔都建高X米，请问等他工作了m天以后每个防护塔的高度分别是多少？
输入描述:
第一行输入一个整数n,表示防护塔的数量。
第二行输入n个数，表示每个防护塔的初始高度。
第三行输入一个整数m，表示牛可乐的工作天数。
接下来m行每行三个整数a,b,c，表示给第a个塔到第b个塔增建c的高度。
1 <= n,m <= 100, 1 <= a, b <= n, 1 <= c <= 1000
输出描述:
输出一行，包含n个整数，以空格隔开，表示各个防护塔最终的高度。
```
```
示例1
输入
4
1 2 3 4
3
1 2 1
2 3 1
4 4 1

输出
2 4 4 5
```
```
#include<iostream>
using namespace std;
int main(){
   int n,len,i=0,d[105],f[105]={0},a,b,c;
   cin>>n;len=n;
   while(i<n)
        cin>>d[i++];
   cin>>n;
   while(n--){  //核心
    cin>>a>>b>>c;
    f[a-1]+=c;
    f[b]-=c;
   }
   for(int j=1;j<=len;j++)
       f[j]+=f[j-1];
   for(int j=0;j<len;j++)
       cout<<d[j]+f[j]<<" ";
    return 0;
}
```
本站相似题目推荐
[问题 1501: [蓝桥杯][算法提高VIP]分苹果](https://www.dotcpp.com/oj/problem1501.html "问题 1501: [蓝桥杯][算法提高VIP]分苹果")

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言训练-大、小写问题（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

get--->差分数组

评论区

精彩推荐

本人酷爱递归实现很多问题，这里也是

printf基础练习2 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

简单的a+b （C语言代码）

C语言训练-数字母（C语言代码）

1011题解

蚂蚁感冒（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

核桃的数量（C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言训练-大、小写问题 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

get--->差分数组

评论区

精彩推荐

本人酷爱递归实现很多问题，这里也是

printf基础练习2 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

简单的a+b （C语言代码）

C语言训练-数字母 （C语言代码）

1011题解

蚂蚁感冒 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

核桃的数量 （C语言代码）

C语言训练-大、小写问题（C语言代码）

　　评论区

C语言训练-数字母（C语言代码）

蚂蚁感冒（C语言代码）

核桃的数量（C语言代码）