差分 & 前缀和

怼烎@ 2021-10-19 02:44 354阅读 0赞

我们从问题入手。

**入门问题：有已赋值的 n 个数，现在有 m 个指令**

**操作 1： 每一次要求将第 k 个数加上 a；**

**操作 2： 查询第 k 个数字的值。**

**$1 ≤ k ≤ n ≤ 10^5$**

这一题其实用一个数组就可以维护。

--------------------

**问题一：有已赋值的 n 个数，现在有 m 个指令，每一个指令要求查询第 x 个数到第 y 个数的和。**

**$1 ≤ x ≤ y ≤ n,m ≤ 10^5$**

如果暴力求和是会 TLE 的。

那应该如何解决这个问题呢？

这就要引出**前缀和**了。

可以看出，$\\sum\_\{i=x\}^ya\_i = \\sum\_\{j=1\}^ya\_j - \\sum\_\{k=1\}^\{x-1\}a\_k$

所以我们只需要求第一个数到各个数的和即可。

求这些数很容易，O(n) 复杂度递推，接下来就可以 O(1) 查询了。

--------------------

**问题二：有已赋值的 n 个数，现在有 m 个指令，每一次要求将第 x 个数到第 y 个数加上 k，最后求所有数的值。**

**$1 ≤ x ≤ y ≤ n,m ≤ 10^5$**

其实这题分块、线段树、树状数组以及其它的很多算法都可以过这题。

但是请看下一个问题：

**问题三：有已赋值的 n 个数，现在有 m 个指令，每一次要求将第 x 个数到第 y 个数加上 k，最后求所有数的值。**

**$1 ≤ x ≤ y ≤ n,m ≤ 5\*10^6$**

我们发现：这个 5e6 的范围太大了，O(n log n) 以及更慢的复杂度是过不了的。

所以，下一个内容是：

--------------------

### 差分 ###

① 什么是差分？

差分，就是一个通过常数复杂度的标记实现求和及其它应用的一种技巧。

一般适合**静态维护**（前面先运算，最后求值）。

② 差分怎么用？

我们马上举一个例子：

有一个数列：

1  9  2  8  3  7  4  6  5
    tag:　 0  0  0  0  0  0  0  0  0　　// 现在还没有打上标记

现在，我们将第 3 个数到第 5 个数加上 2.

那我们就发现，可以把第 3 个数开始把后面所有的数加上 2，再从第 6 个数开始把后面所有数减去 2 呢，就相当于把第 3 个数到第 5 个数加上 2 了。

然后这么标记：

a[i]:  1  9  2  8  3  7  4  6  5
    tag :  0  0  2  0  0  -2 0  0  0　　// 打上标记*1

请注意，如果我们还是一个一个打上标记，这个算法就会退化。

所以，我们将第一个数打上标记，末尾打上相反标记，然后最后用前缀和处理。

然后，我们再将第 4 个数到第 8 个数减去 1.

按照上面的想法，我们可以从第 4 个数开始把后面所有的数减去 1，在从第 9 个数开始把后面所有的数加上 1.

a[i]:  1  9  2  8  3  7  4  6  5
    tag :  0  0  2 -1  0 -2  0  0  1　　// 打上标记*2

假设指令执行结束，那么我们这样求和：

用一个 sum 数组记录，$sum\_i$ 代表前 i 个数所带的 tag 的和。（即前缀和）

a[i]    :  1  9  2  8  3  7  4  6  5
    tag     :  0  0  2 -1  0 -2  0  0  1　　
    sum[i]  :  0  0  2  1  1 -1 -1 -1  0

最后，我们把 $a\_i$ 加上对应的 $sum\_i$，就是答案了。

时间复杂度 O(n).

### 代码 ###

#include <cstdio>
    #define N 5000010
    typedef long long ll;
    
    ll n, m, x, y, k, a[N], sum[N], sub[N];
    
    inline ll read(){            // 数据范围很大的情况下建议用快读 
        ll num = 0, b = 1;
        char c = getchar();
        while(c < '0' || c > '9'){
            if(c == '-') b = -1;
            c = getchar();
        }
        while(c >= '0' && c <= '9'){
            num = num * 10 + c - '0';
            c = getchar();
        }
        return num * b;
    }
    
    int main(){
        
        n = read(), m = read();
        
        for(ll i=1; i<=n; i++)
            a[i] = read();
            
        while(m--){
            x = read(), y = read(), k = read();
            sub[x] += k;
            sub[y + 1] -= k;    // 注意是 y + 1, 因为第 y 个数也要加 k
        }
        
        for(ll i=1; i<=n; i++)
            sum[i] = sum[i - 1] + sub[i];        // 前缀和 
            
        for(ll i=1; i<=n; i++)
            printf("%d ", a[i] + sum[i]);
    
        return 0;
    }

--------------------

## 总结 ##

与其说这是一个算法，不如说这是一个思想。

我们会碰到很多这样的题目，看似需要比较复杂的数据结构，其实很简单。

这需要我们灵活运用所学的知识。

转载于:https://www.cnblogs.com/zengpeichen/p/11279207.html