差分算法详解

一、什么是差分算法

差分算法是一种将区间内的修改和查询问题转化为单点修改问题的算法，用于优化时间复杂度。

举个例子：对于长度为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 <= r; i++) {
        sum += d[i];
        res = min(res, sum);
        if (sum > 0) {
            sum = 0;
        }
    }
    return res;
}

三、差分算法实战

1、LeetCode 1395 统计作战单位数

给定一个数组rating，表示N个士兵的等级。其中rating[i]的值表示第i个士兵的等级。统计其中仅满足条件之一的正确三元组的数量： rating[i] < rating[j] < rating[k] 或者 rating[i] > 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 <= y) return tree[k];
        int mid = (l + r) >> 1, res = 0;
        if (x <= mid) res += query(k << 1, l, mid, x, y);
        if (y > 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 <= n; i++) {
        int x;
        cin >> x;
        diff[x]++; //差分数组记录每个课程的被选择次数
    }
    int res = 0;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        if (diff[x] > 0) { //如果该课程有人选择
            diff[x]--; //差分数组减一
            res++; //结果加一
        }
    }
    cout << res << endl;
    return 0;
}

四、结束语

差分算法是一种非常重要且实用的算法，在优化时间复杂度方面起到了非常好的作用。需要注意的是，在使用差分算法时需要保证数据之间的差分具有可加性，否则可能会出现错误的结果。

差分算法可以应用于很多问题中，包括区间求和、区间最大值、区间最小值等等，它们都可以通过差分数组的前缀和来进行求解。

通过本文的阐述，在实际问题中的应用差分算法也不再是神秘的了，进行差分计算时考虑可加性，避免数据失真。利用差分算法可以减少时间复杂度，让算法更加高效。