首页 > 试题广场 >

【模板】差分

[编程题]【模板】差分

热度指数：874 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，你需要维护：
${\hspace{22.5pt}}_\texttt{1.}\$ 区间修改：将 $[l,r]$ 这个区间中的全部元素增加 $x$ ；
$\hspace{15pt}$ 在全部修改完成后，直接输出最终的数组。

输入描述:

第一行输入两个整数  代表数组中的元素数量、操作次数。
第二行输入  个整数  代表初始数组。
此后  行，每行输入三个整数  代表一次修改。

输出描述:

在一行上输出  个整数，代表最终的数组。

示例1

输入

6 2
1 1 4 5 1 4
1 6 -3
4 4 1

输出

-2 -2 1 3 -2 1

说明

对于第一次操作，数组变为 （全局修改）；
对于第二次操作，数组变为 （单点修改）。

算法知识视频讲解

C++

WasserSingen

//新手一看就懂的方法
#include <iostream>
using namespace std;

int main() {
    int n,q;cin>>n>>q;
    int a,c;long long b[n];
    cin>>a;b[0]=a;
    for(int i=1;i<n;i++){
        cin>>c;
        b[i]=c-a;    //记录每个数与前一个数的差值即为差分
        a=c;
    }
    while(q--){
        int l,r,d;cin>>l>>r>>d;
        b[l-1]+=d;b[r]-=d;//重点！！！对区间进行加减操作等效于对该区间的差分数组的首部加d
	                      //并对尾部后一个的位置减d
    }long long ans=b[0];cout<<ans<<" ";
    for(int i=1;i<n;i++){
        ans+=b[i];    //还原差分数组即为答案
        cout<<ans<<" ";
    }
}

发表于 2026-04-19 01:28:55 回复(0)