算法总结——差分

program_xwl · 2024-07-07 20:42:36 · 算法·理论

差分是前缀和的逆运算，是一种对查询少，而区间修改多的数组的一种优化。

差分定义：

diff_i = a_i-a_{i-1}

对于diff_1，按照公式需要调用无效元素a_0，但由于a_0自动为0，所以一般不特判a_0的情况。

区间修改：

假如需要对a数组进行进行T次修改，每次将区间[L,R]全部加上v。

看到这个，肯定不难想到暴力写法

for(int i = L;i <= R;i++) a[i] += v;

很容易发现，该写法修改一次的时间复杂度就是O(n),T次修改就是O(Tn)如果范围大一点，就会TLE，有没有快点的方法呢？有，那就是差分：

首先，我们对a数组做一次差分，按照公式diff_i = a_i-a_{i-1}，我们可以以。O(n)的时间求出差分数组。

代码：

for(int i = 1;i <= n;i++) diff[i] = a[i]-a[i-1];

接着就是区间修改了，假设我们要将区间[3,5]全部加上3，可以用表格对比一下

可以发现差分数组只有下标为L、R的位置发生了改变，这一现象很容易通过减法的基本性质证明。于是，求出区间修改后的差分数组代码如下：

diff[L] += v;
diff[R] -= v;

最后就是求出原数组了，我们知道diff_i = a_i-a_{i-1}，那么我们很容易推导出a_i=diff_i+a_{i-1}，那a_{i-1}又是多少呢？我们知道diff_1=a_1，于是，我们可以通过递推的方式求出原数组。代码如下：

for(int i = 1;i <= n;i++) diff[i] = a[i-1]+diff[i]

看了上面的原理和代码，可以看出差分数组求出的时间复杂度是O(n)，一次区间修改是O(1)，推出原数组是O(n)，总体就是O(n+t)，比暴力快多了。

例题1：P2367 语文成绩

这题是差分模板题，上面讲的很清楚了。

代码：

#include <bits/stdc++.h>
using namespace std;

int a[5000005],diff[5000005],n,p,mini = 1e9,pre[5000005];

int main(void)
{
    cin >> n >> p;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        diff[i] = a[i]-a[i-1];
    }
    for(int i = 1;i <= p;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        diff[x] += z;
        diff[y+1] -= z;
    }
    for(int i = 1;i <= n;i++)
    {
        pre[i] = pre[i-1] + diff[i];
        mini = min(pre[i],mini);
    }
    cout << mini;
    return 0;
}

例题2 Extreme Subtraction

CF出生的绿题居然只有10个点

题意：给出a数组，可以进行如下两种操作，问有没有可能将数组变为全0。

1. 选择前k个数，将它们全部减1
2. 选择后k个数，将它们全部减1

   思路：先求出差分数组，两个操作可以变成如下

3. diff_1-1$同时$diff_k+1
4. #### 那么成功条件就变为了$diff$数组的区间$[2,n]$变为全零且$0 \le diff_1$。 #### 要怎么让$diff$数组变为全$0$呢？我们可以分3种情况处理：
5. diff_i < 0$：用操作1消耗$diff_1$把它补成$0
7. diff_i > 0$：用操作2把它减成$0

   如果你看懂上面的东西，你就会发现，真正决定是否可以完成操作的其实只有情况1，因为它需要消耗diff_1，diff_1可能会不够用。于是，我们只要将所有需要消耗diff_1的值全部加起来，看看diff_1够不够用，就知道行不行了。

   思路绕来绕去，代码其实挺简单的：

   
   #include <bits/stdc++.h>
   using namespace std;

int T,n,a[30005],diff[30005];

int main(void) { cin >> T; while(T--) { cin >> n; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i <= n;i++) diff[i] = a[i] - a[i-1]; int sum = 0; for(int i = 2;i <= n;i++) { if(diff[i] < 0) sum += diff[i]; } if(abs(sum) <= diff[1]) cout << "YES\n"; else cout << "NO\n"; } return 0; }

### 差分这个算法，只让你【区间修改】的话都没什么难度，但它的思路绕个弯可以出很难得题目。