【10. 差分】

简介: 前缀和主要是计算数组中的某个区间 [ l, r ],中间的所有数的和。>而差分主要是为了计算在[ l, r ]这个区间中所有的数全部加上一个常数c。>## 优点:>正常遍历数组中[ l , r ]区间的话,需要的是o(n)的复杂度,但是使用差分直接是o(1)的复杂度。差分只需要俩步计算。

一维差分

  • 前缀和与差分是逆运算

例如:

数组 a1 , a2,a3,a4,a5 ,....,an
构造 b1,b2,b3,b4,b5,...,bn
使得 ai = b1 + b2 + b3 + b4 + .. + bi。
c此时 ai叫做 bi的前缀和,b 叫做 ai的差分.

差分的用途:

前缀和主要是计算数组中的某个区间 [ l, r ],中间的所有数的和。
而差分主要是为了计算在[ l, r ]这个区间中所有的数全部加上一个常数c。

优点:

正常遍历数组中[ l , r ]区间的话,需要的是o(n)的复杂度,但是使用差分直接是o(1)的复杂度。差分只需要俩步计算。

步骤:

  1. 要对数组 a的 [ l , r]区间的所有数全部加 +1,等价于b[ l ] + 1,(因为a数组是b数组的前缀和,bl +1,相当于把数组a中下标 > l 的所有数全部 +1)
  2. 但是我们希望的是只对[ l , r] 这个区间数+1,经过上述运算,r后面的数也同时 +1,此时通过b[ r + 1] 进行 -1 操作。

图解

1661150749888.png

题目

输入一个长度为 n 的整数序列。

接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 l,r 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数,表示整数序列。

接下来 m 行,每行包含三个整数 l,r,c表示一个操作。

输出格式

共一行,包含 n 个整数,表示最终序列。

数据范围

1 ≤ n,m ≤ 100000
1 ≤ l ≤ r ≤ n
−1000 ≤ c ≤ 1000
−1000 ≤ 整数序列中元素的值 ≤1000

输入样例:

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例:

3 4 5 3 4 2

代码

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int a[N], b[N], s[N];

void insert(int l, int r, int c)              //核心公式
{
   b[l] += c;
   b[r + 1] -= c;
}
int main()
{
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; i ++) scanf("%d", &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 ++)
   {
       a[i] += b[i];
       cout << a[i] << " ";
   }
   return 0;
}
目录
相关文章
|
9月前
|
人工智能 移动开发
差分题练习(区间更新)
差分题练习(区间更新)
|
9月前
|
机器学习/深度学习
FFT能量归一化
FFT能量归一化
175 0
|
传感器
全差分运算放大器
全差分运算放大器(Fully Differential Operational Amplifier,简称FDA)是一种特殊的运算放大器,具有两个差分输入和两个差分输出。它的输入和输出均为差分信号,可以用于放大差分信号、抑制共模信号、降低噪音等。
243 0
|
人工智能 BI
【差分数组】
【差分数组】
|
算法
通过白噪声的频谱处理产生任意光谱斜率(f^a)噪声(Matlab代码实现)
通过白噪声的频谱处理产生任意光谱斜率(f^a)噪声(Matlab代码实现)
110 0
|
传感器 前端开发
BJT差分式放大电路的介绍
一、基本原理 BJT差分式放大电路的基本原理是利用两个晶体管的共射极配置来放大差分输入信号。其中一个晶体管作为输入管,另一个晶体管作为负载管。当差分输入信号的差值发生变化时,输入管的基极电压也会发生变化,导致输入管的电流变化。负载管通过负载电阻来接收输入管的电流变化,并产生相应的输出电压。因此,BJT差分式放大电路可以将差分输入信号放大为差分输出信号。 二、电路结构 BJT差分式放大电路通常由两个晶体管、两个输入电阻、一个负载电阻和一个电源组成。其中,两个晶体管的发射极通过两个输入电阻与差分输入信号相连,基极通过电源与地相连。负载电阻通过两个晶体管的集电极与电源相连,输出信号通过负载电阻与地相
459 0
|
算法
【使用维纳滤波进行信号分离】基于维纳-霍普夫方程的信号分离或去噪维纳滤波器估计(Matlab代码实现)
【使用维纳滤波进行信号分离】基于维纳-霍普夫方程的信号分离或去噪维纳滤波器估计(Matlab代码实现)
253 0
|
机器学习/深度学习 传感器 算法
【滤波】基于平方根无迹卡尔曼滤波SR-UKF实现信号去噪附matlab代码
【滤波】基于平方根无迹卡尔曼滤波SR-UKF实现信号去噪附matlab代码
|
人工智能 算法 安全
【基础算法】差分的应用(一维差分和二维差分)
【基础算法】差分的应用(一维差分和二维差分)
229 0

热门文章

最新文章