差分①

_yang_yi_bo_ · 2024-07-07 13:15:34 · 算法·理论

差分简述

前缀和

说到差分，我们先来说一下前缀和。

还记得什么是前缀和吗？它是静态求前缀和的一种工具。sum_i =a_1+a_2+a_3+...+a_i，进行 t 次求区间和，时间复杂度仅为 O(t)。

差分

我们在来说差分，它被应用于多次修改区间。差分数组 diff_i=a_i-a_{i-1}，也就是记录了当前元素与前一个元素的差。

那他它有什么应用呢？

如下图，我们将区间 a_{[2,4]} 分别加上了 2 结果差分数组只在 diff_2 加上了 2，diff_5 减去了 2。可见，差分可以用 O(1) 的时间复杂度对区间进行修改。

还有一个性质：

如下图，我们将 a 的差分数组进行取前缀和后，变回了原来的数组。

运用这两个性质，我们可以解决很多问题。

U69096 前缀和的逆

这题并不是很困难，我们运用性质二，用 a_i-a_{i-1} 就行了。

#include<bits/stdc++.h> 
using namespace std;
int n;
int a[10005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }for(int i=1;i<=n;i++){
        cout<<a[i]-a[i-1]<<" ";
    }
    return 0;
}

P2367 语文成绩

这题就是简单的差分板子题。

#include<bits/stdc++.h> 
using namespace std;
int n,m,ans=2e9+5;
int a[10000005],diff[10000005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        diff[i]=a[i]-a[i-1];
    }for(int i=1;i<=m;i++){
        int l,r,v;
        cin>>l>>r>>v;
        diff[l]+=v;
        diff[r+1]-=v;
    }for(int i=1;i<=n;i++){
        diff[i]+=diff[i-1];
        ans=min(ans,diff[i]);
    }cout<<ans;
    return 0;
}

接下来的两道题难度偏高。

CF1442A Extreme Subtraction

让所有的差分数组归零，就能让整个数组全部归零。

在 diff_i ≥ 0 时，就一定能让这个数归零。

比如 a 数组为 1，2，3 时，很容易构造出如何让所有数归零。