数据结构--差分数组（含题目）＜基础入门＞

定义：差分数组是一种处理数据的技巧，主要用于高效地执行区间修改操作。在一个数组中，如果需要频繁地对某个区间的所有元素执行相同的操作（如加或减一个常数），直接遍历并更新区间内的每个元素会非常耗时。差分数组通过只修改区间的端点来实现整个区间的快速更新，大幅降低了操作的时间复杂度。

简单来说，差分数组被创造用来处理区间的加减问题（我是这么理解的），所以以后如果在题目中看到对某一个区间的所有数进行加减操作的，可以先想到运用差分数组来思考。如果向更加深入的了解差分数组的本质，可以自己通过阅读书籍。先来看一个差分入门的题目：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];//原数组
int d[N];//差分数组
int n,m;
void revise(int l,int r,int c){
    d[l]+=c;
    d[r+1]-=c;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) revise(i,i,a[i]);
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        revise(l,r,c);
    }
    for(int i=1;i<=n;i++){
        d[i]+=d[i-1];
    }
    for(int i=1;i<=n;i++) cout<<d[i]<<" ";
}

上面这个题目是对一个区间进行加操作，完成后输出原数组。我们只需要在区间的开头加上这个数，然后在区间结尾的下一个数减去这个数就可以了。因为差分数组其实是前缀和的逆运算。举个例子，假设原数组是a，差分数组是b，则有a[0] = b[0]，b[1] = a[1] - a[0]，b[2] = a[2] - a[1]，....以此类推，假设初始化完差分数组的时候，如果我们需要得到a[2]，那么就是a[2] = b[2] + b[1] + b[0]。毫无疑问，这就是算差分数组的前缀和。回到上面，假设区间为[l, r]，在b[l]上加c，相当于从l开始到结尾的数都加上了c，在b[r + 1]减去了c，相当于从r+1开始到结尾都减去了c，这就实现了区间[l,r]上的加c操作而没有影响到其他的数。模板就是上面的reverse函数：

void revise(int l,int r,int c){
    d[l]+=c;
    d[r+1]-=c;
}

接下来是一些leetcode上面的题目，对于理解差分数组有很大的帮助。

2848. 与车相交的点

这道题目是典型的差分数组，主要思路是给每个区间上都加上1，累计答案时判断如果此时这个点的值大于0，则说明被覆盖了。以下是我的代码：

Python：

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        max_end = max(end for _, end in nums)
        diff = [0] * (max_end + 2)
        for s, e in nums:
            diff[s] += 1
            diff[e + 1] -= 1
        s = 0 #用来计算前缀和
        res= 0
        for c in range(max_end + 1):
            s += diff[c]
            if (s > 0):
                res += 1
        return res  

C++：

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        maxx = (max(end for _, end in nums) + 1)
        a = [0] * (maxx + 2)
        for start, end in nums:
            a[start] += 1
            a[end + 1] -= 1
        return sum(s > 0 for s in accumulate(a))
            

1893. 检查是否区域内所有整数都被覆盖

这个题 和上面的题目大同小异，主要的思路就是：用差分数组的思想将range数组里面的区间上的数都标记一遍，最后算答案的时候遍历，看[left, right]区间上的数是否有a[x] <= 0的，如果有，返回false，反之，返回True。

Python:

class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        max_end = max(end for _, end in ranges)
        a = [0] * (max_end + 2)
        for start, end in ranges:
            a[start] += 1
            a[end + 1] -= 1
        for i in range(1, max_end + 2):
            a[i] += a[i - 1]
        for x in range(left, right + 1):
            if x >= max_end + 2 or a[x] <= 0:
                return False
        return True

C++:

class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        int max_end = std::ranges::max(ranges, {}, [](const auto& a) {
            return a[1];
        })[1];
        vector<int> diff(max_end + 2);
        for (auto x: ranges) {
            diff[x[0]] += 1;
            diff[x[1] + 1] -= 1;
        }
        for (int i = 1; i < max_end + 2; i ++) {
            diff[i] += diff[i - 1];
        }
        for (int x = left; x <= right; x ++ ) {
            if (x >= max_end + 2 || diff[x] <= 0) {
                return false;
            }
        }
        return true;
    }
};

1854. 人口最多的年份

主要思路是： 用一个数组a来统计logs上区间上的点出现的次数，如果最后从小到大遍历年份，算出出现次数最多的年份即可。

Python：

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        offset = 1950
        a = [0] * 101
        for s, e in logs:
            a[s - offset] += 1
            a[e - offset] -= 1
        mx = 0
        res = 0
        cur = 0
        for i in range(101):
            cur += a[i]
            if cur > mx:
                mx = cur
                res = i
        return res + offset

C++：

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<int> mi_vector = std::ranges::min(logs, {}, [](auto& x) {
            return x[0];
        });
        int mi = mi_vector[0];
        vector<int> mx_vector = std::ranges::max(logs, {}, [](auto& x) {
            return x[1];
        });
        int mx = mx_vector[1];
        vector<int> a(mx + 2);
        for (auto x: logs) {
            a[x[0]] += 1;
            a[x[1]] -= 1; 
        }
        int res = 0, diff = 0;
        int s = 0;
        for (int i = mi; i <= mx; i ++) {
            s += a[i];
            if (s > diff) {
                res = i;
                diff = s;
            }
        }
        return res;
    }
};

改良后的版本，速度快了。

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        // vector<int> mi_vector = std::ranges::min(logs, {}, [](auto& x) {
        //     return x[0];
        // });
        // int mi = mi_vector[0];
        // 换了一种求最小(大)值的方法，速度变快了很多
        auto mi = std::ranges::min_element(logs, {}, [](const auto& x) {
            return x[0];
        });
        // vector<int> mx_vector = std::ranges::max(logs, {}, [](auto& x) {
        //     return x[1];
        // });
        // int mx = mx_vector[1];
        auto mx = std::ranges::max_element(logs, {}, [](const auto& x) {
            return x[1];
        });
        vector<int> a((*mx)[1] + 2);
        for (auto x: logs) {
            a[x[0]] += 1;
            a[x[1]] -= 1; 
        }
        int res = 0, diff = 0;
        int s = 0;
        for (int i = (*mi)[0]; i <= (*mx)[1]; i ++) {
            s += a[i];
            if (s > diff) {
                res = i;
                diff = s;
            }
        }
        return res;
    }
};

2960. 统计已测试设备

 这个题目和以往直接对区间进行加减操作的题目有一点不一样，就是只有在 

s + batteryPercentages[i] <= 0

的时候才会进行处理，不过思想也都是一样的。

Python:

class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        n = len(batteryPercentages)
        cnt = [0] * (n + 1)
        ans = s = 0
        for i in range(n):
            s += cnt[i]
            if (s + batteryPercentages[i] <= 0):
                ans += 1
            else:
                cnt[i + 1] -= 1
        return n - ans

C++:

class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int n = batteryPercentages.size();
        vector<int> cnt(n + 1);
        int ans = 0;
        int s = 0;
        for (int i = 0; i < n; i ++) {
            s += cnt[i];
            if (s + batteryPercentages[i] <= 0) {
                ans ++;
            }
            else {
                cnt[i + 1] -= 1;
            }
        }
        return n - ans;
    }
};

1094. 拼车

 这个题目和之前的题目差不多，都是直接对区间进行操作，不再赘述！！！！

Python：

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        mx = max(to for _, _, to in trips)
        a = [0] * (mx + 2)
        s = 0
        for num, fm, to in trips:
            a[fm] += num
            a[to] -= num
        for i in range(mx + 2):
            s += a[i]
            if (s > capacity):
                return False
        return True

C++：

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> x = std::ranges::max(trips, {}, [](const auto& x) {
            return x[2];
        });
        int mx = x[2];
        vector<int> a(mx + 2);
        for (const auto& x: trips) {
            a[x[1]] += x[0];
            a[x[2]] -= x[0];
        }
        int s = 0;
        for (int i = 0; i < mx + 2; i ++) {
            s += a[i];
            if (s > capacity) {
                return false;
            }
        }
        return true;
    }
};

1109. 航班预订统计

Python：

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        a = [0] * (n + 2)
        for l, r, num in bookings:
            a[l] += num
            a[r + 1] -= num
        ans = []
        s = 0
        for i in range(n):
            s += a[i + 1]
            ans.append(s)
        return ans

C++：

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> a(n + 2);
        for (const auto& x: bookings) {
            a[x[0]] += x[2];
            a[x[1] + 1] -= x[2];
        }
        vector<int> ans;
        int s = 0;
        for (int i = 1; i <= n; i ++) {
            s += a[i];
            ans.push_back(s);
        }
        return ans;
    }
};

3355. 零数组变换 I

 Python：

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        n = len(nums)
        a = [0] * (n + 2)
        for l, r in queries:
            a[l] -= 1
            a[r + 1] += 1
        s = 0
        for i in range(n):
            s += a[i]
            if s + nums[i] > 0:
                return False
        return True

C++：

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> cnt(n + 2);
        for (const auto & x: queries) {
            cnt[x[0]] -= 1;
            cnt[x[1] + 1] += 1;
        }
        int s = 0;
        for (int i = 0; i < n; i ++) {
            s += cnt[i];
            if (s + nums[i] > 0) {
                return false;
            }
        }
        return true;
    }
};

• 56. 合并区间

 这个题目有两种解法，一种是贪心+排序，一种是差分数组的解法。在这里讲一下差分数组的解法，这题是一个变种的差分数组。我们需要将范围映射到原来的两倍，不然就会出现错误，例如样例为[1, 4],[5, 6]就会通过不了。做的改变如下：

贪心解法代码：

C++：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() == 0){
            return {};
        }
        sort(intervals.begin(),intervals.end());
        vector<vector<int>>ans;
        for(int i = 0; i < intervals.size(); i ++){
            int l =intervals[i][0], r = intervals[i][1];
            if(!ans.size() || ans.back()[1] < l){
                ans.push_back({l, r});
            }
            else{
                ans.back()[1] = max(ans.back()[1], r);
            }
        }
        return ans;
    }
};

差分数组解法代码：

Python：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        mi = min(s for s, _ in intervals)
        mx = max(e for _, e in intervals)
        diff = [0] * (2 * mx + 2)
        ans = [] 
        for s, e in intervals:
            diff[2 * s] += 1
            diff[2 * e + 1] -= 1
        s, l = 0, -1
        for i in range(len(diff)):
            s += diff[i]
            # 刚开始
            if s > 0:
                if (l == -1):
                    l = i // 2
            # 此时结束了
            elif (s == 0):
                if (l != -1):
                    ans.append([l, i // 2])
                    l = -1
        return ans
"""
intervals = 
[[1,4],[5,6]]
"""

C++：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        auto max_it = std::ranges::max_element(intervals, {}, [](const auto& x) {
            return x[1];
        });
        int mx = (*max_it)[1];
        vector<int> diff(2 * mx + 2);
        for (auto x: intervals) {
            diff[2 * x[0]] += 1;
            diff[2 * x[1] + 1] -= 1;
        }
        vector<vector<int>> ans;
        int l = -1; //起点
        int s = 0;
        for (int i = 0; i <= 2 * mx + 1; i ++) {
            s += diff[i];
            if (s > 0) {
                if (l == -1) {
                    l = i / 2;
                }
            }
            else if (s == 0) {
                if (l != -1) {
                    ans.push_back({l, (i) / 2});
                    l = -1;
                }
            }
        }
        return ans;
    }
};

• 57. 插入区间

这题和合并区间大同小异，只是多了一个区间的判断。

 Python：

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        mx = 0
        if len(intervals) > 0:
            mx = max(end for _, end in intervals)
        mx = max(mx, newInterval[1])
        cnt = [0] * (2 * mx + 2)
        for s, e in intervals:
            cnt[s * 2] += 1
            cnt[e * 2 + 1] -= 1
        cnt[2 * newInterval[0]] += 1
        cnt[2 * newInterval[1] + 1] -= 1
        ans, l , s = [], -1, 0
        for i in range(len(cnt)):
            s += cnt[i]
            if s > 0:
                if (l == -1):
                    l = i // 2
            else:
                if (l != -1):
                    ans.append([l, i // 2])
                    l = 0
        return ans

C++：

    class Solution {
    public:
        vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
            vector<int> mx;
            if (intervals.size() > 0) {
                vector<int> mx = std::ranges::max(intervals, {}, [](const auto& x) {
                    return x[1];
                    });
            }
            vector<vector<int>> ans;
            vector<int> diff(2 * max(mx[1], newInterval[1]) + 2);
            for (const auto& x: intervals) {
                diff[2 * x[0]] += 1;
                diff[2 * x[1] + 1] -= 1;
            }
            diff[2 * newInterval[0]] += 1;
            diff[2 * newInterval[1]  + 1] -= 1;
            int s = 0, start = -1;
            for (int i = 0; i < diff.size(); i ++) {
                s += diff[i];
                if (s > 0) {
                    if (start == -1) {
                        start = i / 2;
                    }
                }
                else if (s <= 0) {
                    if (start != -1) {
                        ans.push_back({start, i / 2});
                        // 重新找一个区间的开始位置，需要重新定义一下，而不是直接初始化为i / 2
                        start = -1;
                    }
                }
            }
            return ans;
        }
    };

• 732. 我的日程安排表 III

 主要思路是：统计每一个区间上每一个点出现的次数，然后每一个使用book方法时，输出最大值。统计的方法用差分数组来统计！！！！！

C++：

class MyCalendarThree {
map<int, int> cnt;
public:
    MyCalendarThree() {
    }
    
    int book(int startTime, int endTime) {
        cnt[startTime] += 1;
        cnt[endTime] -= 1; 
        int total = 0, ans = 0;
        for (auto [x, y]: cnt) {
            total += y;
            ans = max(ans, total);
        }
        return ans;
    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(startTime,endTime);
 */

Python：

class MyCalendarThree:

    def __init__(self):
        self.cnt = SortedDict()

    def book(self, startTime: int, endTime: int) -> int:
        ans = total = 0
        self.cnt[startTime] = self.cnt.get(startTime, 0) + 1
        self.cnt[endTime] = self.cnt.get(endTime, 0) - 1
        for x in self.cnt.values():
            total += x
            ans = max(ans, total)
        return ans


# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)

差分数组的练习暂且到此为止了，后续还会持续更新差分数组的题目！如果看到这里想必你也很累了吧，休息一下！！再继续学习！！