差分算法詳解

一、什麼是差分算法

差分算法是一種將區間內的修改和查詢問題轉化為單點修改問題的算法，用於優化時間複雜度。

舉個例子：對於長度為n的數組a，如果需要對區間[l,r]內的所有數加上k，那麼簡單直接的做法是遍歷[l,r]，每個數加上k，時間複雜度O(r-l+1)。如果有很多個這樣的操作，時間複雜度將變得非常高。而差分算法可以將這些區間修改操作轉化為對於兩個單點的修改操作，即a[l]加上k，a[r+1]減去k，時間複雜度變為O(1)。

void diff(int a[], int l, int r, int k) {
    a[l] += k;
    a[r + 1] -= k;
}

二、差分算法的應用

1、區間求和

通過差分算法，將區間求和問題轉化為對單點求和的問題。

void init(int a[], int d[], int n) {
    d[1] = a[1];
    for (int i = 2; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
    }
}

int sum(int d[], int l, int r) {
    int res = 0;
    for (int i = l; i <= r; i++) {
        res += d[i];
    }
    return res;
}

2、區間最大值

區間最大值問題可以通過差分數組的前綴和來進行求解。

void init(int a[], int d[], int n) {
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
    }
}

int max(int d[], int l, int r) {
    int res = 0, sum = 0;
    for (int i = l; i <= r; i++) {
        sum += d[i];
        res = max(res, sum);
        if (sum < 0) {
            sum = 0;
        }
    }
    return res;
}

3、區間最小值

區間最小值問題同樣可以通過差分數組的前綴和來進行求解。

void init(int a[], int d[], int n) {
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
    }
}

int min(int d[], int l, int r) {
    int res = 0, sum = 0;
    for (int i = l; i  0) {
            sum = 0;
        }
    }
    return res;
}

三、差分算法實戰

1、LeetCode 1395 統計作戰單位數

給定一個數組rating，表示N個士兵的等級。其中rating[i]的值表示第i個士兵的等級。統計其中僅滿足條件之一的正確三元組的數量： rating[i] < rating[j] rating[j] > rating[k] ，其中0 <= i < j < k < N。

class Solution {
public:
    int diff[200005] = {0};
    int tree[800005] = {0};
    int n;
    
    void update(int k, int l, int r, int x, int val) {
        if (l == r) {
            tree[k] += val;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) update(k << 1, l, mid, x, val);
        else update(k << 1 | 1, mid + 1, r, x, val);
        tree[k] = tree[k << 1] + tree[k << 1 | 1];
    }
    
    int query(int k, int l, int r, int x, int y) {
        if (x <= l && r > 1, res = 0;
        if (x <= mid) res += query(k < mid) res += query(k << 1 | 1, mid + 1, r, x, y);
        return res;
    }
    
    int numTeams(vector& rating) {
        n = rating.size();
        for (int i = 0; i < n; i++) update(1, 1, n, rating[i], 1);
        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            int l = query(1, 1, n, 1, rating[i] - 1), r = query(1, 1, n, rating[i] + 1, n);
            int ll = query(1, 1, n, 1, rating[i] - 1), rr = query(1, 1, n, rating[i] + 1, n);
            res += l * rr + r * ll;
        }
        return res;
    }
};

2、課程設計分組

現在有n個學生和m個課程，每個學生都有一些感興趣的課程，課程可能會有多個學生感興趣。我們需要根據學生感興趣的課程，將學生分成若干組，每組至少包含一個不同的課程。請編寫一個分組函數，使得分出最多的組。

int diff[100005] = {0};

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i > x;
        diff[x]++; //差分數組記錄每個課程的被選擇次數
    }
    int res = 0;
    for (int i = 1; i > x;
        if (diff[x] > 0) { //如果該課程有人選擇
            diff[x]--; //差分數組減一
            res++; //結果加一
        }
    }
    cout << res << endl;
    return 0;
}

四、結束語

差分算法是一種非常重要且實用的算法，在優化時間複雜度方面起到了非常好的作用。需要注意的是，在使用差分算法時需要保證數據之間的差分具有可加性，否則可能會出現錯誤的結果。

差分算法可以應用於很多問題中，包括區間求和、區間最大值、區間最小值等等，它們都可以通過差分數組的前綴和來進行求解。

通過本文的闡述，在實際問題中的應用差分算法也不再是神秘的了，進行差分計算時考慮可加性，避免數據失真。利用差分算法可以減少時間複雜度，讓算法更加高效。