差分

我不是女神ヾ 2021-11-01 10:04 351阅读 0赞

### 概念 ###

对于一个数组a\[n\]，有m次操作，都是对区间\[l,r\]加上k，完事后输出数组

在知道第一个数a\[1\]的情况下，如果我们知道后面的数与前一个数的差值p，那么就能还原原数组，即

for(int i = 2; i <= n; ++i) a[i] = a[i - 1] + p[i];//还原

for(int i = 1; i <= n; ++i) p[i] = a[i] - a[i - 1];//get p

### 细节 ###

对于区间操作，一个区间都加上k，即最左边的数a\[l\]比它前一位多了k，即p\[l\] += k;

最右边的数a\[r\]比它后一位多了k，则它后一位比它少了k，即p\[r + 1\] -= k;

区间内各个数之间的差值不变，例如1和2差1，都加上5变成6和7，还是差1，所以只是改两端即可。

### 代码 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100001;
    
    int n,m;
    int a[N],pl[N];
    
    int main(){
        cin >> n >> m;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = 1; i <= n; ++i) pl[i] = a[i] - a[i - 1];
        for(int i = 1, z, l, r, y; i <= m; ++i){
            cin >> z >> l >> r >> y;
            if(z == 1){
                pl[l] += y;
                pl[r + 1] -= y;
            }
            for(int i = 1; i <= n; ++i) a[i] = a[i - 1] + pl[i];
            for(int i = 1; i <= n; ++i) cout << a[i] << " "; 
        }
        return 0;
    }

###      ###

转载于:https://www.cnblogs.com/Adventurer-H/p/11230189.html

发表评论取消回复

表情：

评论列表（有 0 条评论，351人围观）

还没有评论，来说两句吧...

相关阅读

相关前缀和与差分 AcWing 798. 差分矩阵

前缀和与差分 AcWing 798. 差分矩阵原题链接 [AcWing 798. 差分矩阵][AcWing 798.] 算法标签差分思路 ![

淩亂°似流年/ 2023年09月28日 11:16/ 0 赞/ 25 阅读

相关一阶差分与二阶差分及还原

一阶差分与二阶差分及还原一阶差分 arr = np.arange(10) np.random.shuffle(arr) arr = pd.

比眉伴天荒/ 2022年10月06日 11:53/ 0 赞/ 599 阅读

相关差分差分差分

class Solution { public: / 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可返回m天后

我不是女神ヾ/ 2022年08月31日 02:15/ 0 赞/ 269 阅读

相关差分思想（精辟）

首先介绍差分思想：设数组a\[\]=\{1,6,8,5,10\}，那么差分数组b\[\]=\{1,5,2,-3,5\} 也就是说b\[i\]=a\[i\]-a\[i-1\

忘是亡心i/ 2022年03月15日 15:26/ 0 赞/ 255 阅读

相关差分信号解释

所谓差分方式传输，就是发送端在两条信号线上传输的幅值是相等的，相位是相反的电信号，如下图所示： ![20171222175545054][] 而对于接收端，

小咪咪/ 2022年01月14日 22:53/ 0 赞/ 288 阅读

相关基础算法--差分

输入一个长度为n的整数序列。接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中\[l, r\]之间的每个数加上c。请你输出进行完所有操作后的序列。

谁践踏了优雅/ 2021年12月03日 16:11/ 0 赞/ 295 阅读

相关【2019.7.10】树上差分杂[LCA 倍增][树上差分点差分边差分]

多用于记录树上节点被经过的次数,记录某条边被经过的次数的时候点差分 [P3128 \[USACO15DEC\]最大流Max Flow][P3128_ _US

迷南。/ 2021年11月17日 15:44/ 0 赞/ 330 阅读

相关差分

概念对于一个数组a\[n\]，有m次操作，都是对区间\[l,r\]加上k，完事后输出数组在知道第一个数a\[1\]的情况下，如果我们知道后面的数与前一个数的差值p，

我不是女神ヾ/ 2021年11月01日 10:04/ 0 赞/ 352 阅读

相关差分约束系统

差分约束系统前言:在清北学堂模拟赛的差分约束题写炸了，感觉有必要来总结一下差分约束问题模型 -------------------- 求解由若干不等式限制的

偏执的太偏执、/ 2021年10月29日 13:34/ 0 赞/ 396 阅读

相关差分 & 前缀和

我们从问题入手。入门问题：有已赋值的 n 个数，现在有 m 个指令操作 1：每一次要求将第 k 个数加上 a；操作 2：查询第 k 个数字的值。 $1

怼烎@/ 2021年10月19日 02:44/ 0 赞/ 385 阅读