AcWing-797. 差分刷题笔记（c++）

浅浅的花香味﹌ 2023-02-25 10:20 17阅读 0赞

#### 写在前面 ####

*  难度：简单
 *  知识盲点，学习新的算法思想
    
     *  相关文章很多，不再赘述

#### 题目详情 ####

输入一个长度为n的整数序列。
    
    接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。【这里l、r表示下标】
    
    请你输出进行完所有操作后的序列。
    
    输入格式
    第一行包含两个整数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

#### ac代码 ####

*  差分思想
    
     *  举例：数组a\[\]=\{1,6,8,5,10\}，那么差分数组b\[\]=\{1,5,2,-3,5\}
        
         *  `b[i]=a[i]-a[i-1]; (a[0]=0;)`
         *  `a[i]=b[1]+....+b[i];` 【**问题重点**】
         *  当要改变区间\[ 2, 4 \]时，对于b数组，只要改变 b\[ 2 \] 和 b\[ 4+1 \]
         *  即对区间\[x,y\]进行修改,只用修改b\[x\]与b\[y+1\]:
            
             *  `b[x]=b[x]+k; b[y+1]=b[y+1]-k;`

#include<iostream>
    
    using namespace std;
    
    const int N = 1e5+10;
    int a[N], b[N];
    // 将原始数据读入数组，差分计算
    void loadb(int b[], int l, int r, int c)
    {
        
        b[l] += c;
        b[r+1] -= c;
    }
    
    int main()
    {
        
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++)
        {
        
            scanf("%d", &a[i]);
            loadb(b, i, i, a[i]);
        }
    
        int l, r, c;
        while(m--)
        {
        
            scanf("%d%d%d", &l,&r,&c);
            loadb(b, l, r, c);
        }
        // 差分计算后数组
        for(int i=1; i<=n; i++)
        {
        
            a[i] = a[i-1] + b[i];
            printf("%d ", a[i]);
        }
        return 0;
    }

*  参考文章
    
     *  [AcWing 797.差分][AcWing 797.]

[AcWing 797.]: https://www.cnblogs.com/fsh001/p/12248066.html