题目描述

题目大意&链接

在一个给定的 n 个元素的数列中，将 [l, r]之间的元素都加上c（循环遍历时间复杂度为 O(n) 可能会超时，采用差分解决类似的问题可以降低时间复杂度至 O(1)）。

输入输出样例：
输入：

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

输出：

3 4 5 3 4 2

详情：ac_797差分

解题思路

首先差分和前缀和思想是互逆的，前缀和是求子区间和，差分是在子区间每个元素上加上元素 c。

输入数组 a ，得到它的差分 b 数组：

for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
//b[i] = a[i] - a[i-1] a数组是b数组的前缀和，b数组是a数组的差分
for(int i = 1; i <= n; i++) insert(i, i, a[i]);
...
//对区间 [l, r] 加 c 时，只需 b[l] += c 和 b[r+1] -= c，将区间操作转换为端点操作。
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r+1] -= c;
}

输出结果时，将 b 数组还原成前缀和数组：

//还原成前缀和数组
for(int i = 1; i <= n; i++) b[i] += b[i-1];
for(int i = 1; i <= n; i++) printf("%d ", b[i]);

完整代码

#include<iostream>

using namespace std;

const int N = 1e6  + 10;

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

//对区间 [l, r] 加 c 时，只需 b[l] += c 和 b[r+1] -= c，将区间操作转换为端点操作。
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]);
    //b[i] = a[i] - a[i-1] a数组是b数组的前缀和，b数组是a数组的差分
    for(int i = 1; i <= n; i++) insert(i, i, 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++) printf("%d ", b[i]);
    return 0;
}

时间和空间复杂度

时间复杂度：O(n + m)
空间复杂度：O(n)