#qc003. 差分数组

差分数组

差分数组

题目描述

​ 从键盘输入一个整数 n,再输入 n 个整数。请输出这 n个数的差分数组。

​ 差分数组定义为:对于原数组 a1,a2,…,ana_1,a_2,…,a_n,其差分数组 d1,d2,…,dnd_1,d_2,…,d_n 满足:di=ai−ai−1d_i=a_i−a_{i−1}

​ 其中规定 a0=0a_0=0,因此d1=a1d_1=a_1。

输入格式

​ 第一行,一个正整数 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=1d_1=a_1−a_0=1−0=1
    • d2=a2−a1=2−1=1d_2=a_2−a_1=2−1=1
    • d3=a3−a2=3−2=1d_3=a_3−a_2=3−2=1
    • d4=a4−a3=4−3=1d_4=a_4−a_3=4−3=1
    • d5=a5−a4=5−4=1d_5=a_5−a_4=5−4=1

数据规模与约定

对于 100% 的数据,

1≤n≤1051≤n≤10^5

1≤ai≤1061≤a_i≤10^6

提示

  • 差分是前缀和的逆运算:若 s是 a 的前缀和数组,则 a是 s的差分数组。
  • 差分数组常用于高效处理区间修改问题:对区间 [l,r] 同时加上 v,只需令 dl+=v,dr+1−=vd_l+=v,d_{r+1}−=v,最后做一遍前缀和即可还原数组。
  • 本题中 aia_i均为正整数,但差分值可能为负数(当后一项小于前一项时),因此差分数组建议使用有符号整型存储。