差分數組的定義及用途

一、差分數組的定義

差分數組是一種特殊的數組，是由原數組按照一定規則變換得到的，其元素的值對應著原數組中相鄰元素的差值。假設原數組為A，差分數組為D，則有：

D[i] = A[i] - A[i-1]   (i > 0)
D[i] = A[0]            (i = 0)

其中，D[0]表示A[0]本身，相當於A[0]與A[-1]的差值為0。

差分數組還可以通過反推得到原數組。假設差分數組為D，原數組為A，則有：

A[0] = D[0]
A[i] = A[i-1] + D[i]  (i > 0)

二、差分數組的用途

1. 區間加、區間求和問題

在一些求區間和或計算區間加的問題中，可以通過構造一個差分數組，將問題轉化為對差分數組的處理。例如，給定一個長度為n的數組A和m個操作，每次操作是將區間[l, r]中的元素加上v，求最終A中各元素的值。可以定義一個差分數組D，D[i]表示A[i]與A[i-1]之差，這樣，我們對區間[l, r]進行加v的操作，就相當於將D[l]、D[l+1]、……、D[r]分別加上v。最後，由於A[i] = D[0]+D[1]+……+D[i]，因此，我們可以對差分數組D求一遍前綴和得到最終的A數組。

以下是區間加、區間求和問題的示例代碼：

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

const int N = 100010;
int a[N], d[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1;i > a[i];
    for(int i = 1;i > l >> r >> v;
        d[l] += v;
        d[r+1] -= v;
    }
    for(int i = 1;i <= n;i++)
        d[i] += d[i-1];
    for(int i = 1;i <= n;i++)
        cout << d[i] << " ";
    cout << endl;
    return 0;
}

2. 差分約束系統問題

在一些約束條件下，求解一組變數的最大值或最小值，可以通過差分約束系統來求解。例如，假設存在若干個變數x_i(i = 1,2,……,n)，其中部分變數之間有形如x_i – x_j ≤ d(k為常數)的約束條件，求滿足約束條件的變數x的最大值或最小值。

我們可以使用差分數組來維護這個約束系統。我們定義一個差分數組D，D[i]表示x[i]與x[i-1]之間的差值。因此，如果有形如x[i] – x[j] ≤ d的約束，可以轉換為D[i] ≤ d – D[j]。這樣，我們就可以將差分約束系統轉化為一系列不等式，再使用拓撲排序求解即可。

以下是差分約束系統問題的示例代碼：

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

const int N = 100010, M = 100010, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int d[N], q[N];
bool st[N];
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool check(int mid)
{
    memset(h, -1, sizeof h);
    memset(d, 0, sizeof d);
    memset(st, 0, sizeof st);
    idx = 0;
    for(int i = 1;i  mid) continue;
        add(e[i], e[i]-1, -1);
        add(e[i]-1, e[i], 1);
        d[e[i]] += 1;
    }
    int hh = 0, tt = 0;
    for(int i = 1;i <= n;i++)
        if(!d[i])
            q[tt++] = i, st[i] = true;
    while(hh != tt)
    {
        int t = q[hh++];
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            d[j]--;
            if(d[j] == 0) q[tt++] = j, st[j] = true;
            d[j] = max(d[j], d[t] + w[i]);
        }
    }
    for(int i = 1;i > n >> m;
    for(int i = 1;i > a >> b >> c;
        e[i] = b, ne[i] = h[a], w[i] = c, h[a] = i;
    }
    int l = 0, r = INF;
    while(l > 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

三、總結

差分數組是一種特殊的數組，可以通過原數組變換得到。在一些區間求和或區間加等問題中，差分數組可以幫助我們高效地求解。同時，在差分約束系統問題中，差分數組也可以幫助我們轉換為不等式，從而求解最大值或最小值。因此，熟練掌握差分數組的定義及應用，對於高效解決一些實際問題有著重要的作用。