差分数组
题目描述
从键盘输入一个整数 n,再输入 n 个整数。请输出这 n个数的差分数组。
差分数组定义为:对于原数组 a1,a2,…,an,其差分数组 d1,d2,…,dn 满足:di=ai−ai−1
其中规定 a0=0,因此d1=a1。
输入格式
第一行,一个正整数 n,表示数据的个数。
第二行,n个正整数,用空格隔开,表示原数组。
输出格式
输出一行,n个整数,用空格隔开,表示差分数组。
输入输出样例
5
1 2 3 4 5
1 1 1 1 1
4
10 20 30 40
10 10 10 10
样例解释
- 对于样例 1:
- d1=a1−a0=1−0=1
- d2=a2−a1=2−1=1
- d3=a3−a2=3−2=1
- d4=a4−a3=4−3=1
- d5=a5−a4=5−4=1
数据规模与约定
对于 100% 的数据,
1≤n≤105
1≤ai≤106
提示
- 差分是前缀和的逆运算:若 s是 a 的前缀和数组,则 a是 s的差分数组。
- 差分数组常用于高效处理区间修改问题:对区间 [l,r] 同时加上 v,只需令 dl+=v,dr+1−=v,最后做一遍前缀和即可还原数组。
- 本题中 ai均为正整数,但差分值可能为负数(当后一项小于前一项时),因此差分数组建议使用有符号整型存储。