差分数组
差分数组通常是指一个数组，其中每个元素是原数组中对应元素与前一个元素的差。这种数组在处理序列数据时非常有用，尤其是在需要计算连续项之间的变化或者进行数据压缩时。
定理解释：
差分数组的一个核心定理是，给定一个差分数组，可以唯一地重建原始数组。这意味着，如果你有一个差分数组，你可以通过累加的方式恢复原始数组。这个定理的成立基于以下几个步骤：
差分数组的构建：假设有一个原始数组 A[1…n]，我们可以构建一个差分数组 D[1…n]，其中 D[i] = A[i] - A[i-1]，对于 i = 2, 3, …, n，且 D[1] = A[1]（或者可以选择 D[1] = 0，如果 A[1] 是相对于某个已知的起始值）。
原始数组的重建：给定差分数组 D[1…n]，我们可以重建原始数组 A[1…n]，方法是从 A[1] = D[1] 开始，然后对于每个 i（2 ≤ i ≤ n），计算 A[i] = A[i-1] + D[i]。
这个定理的证明是直接的，因为你可以通过反向操作来验证重建的数组是否与原始数组相同。从 A[1] 开始，使用差分数组中的每个差值逐步累加，最终得到的 A[n] 应该与原始数组的最后一个元素相同。
应用场景：
1.数据压缩：减少存储空间，特别是在数据变化不大时。
2.快速求和：快速计算数组中任意一段区间的和。
3.更新和查询：在数组中快速更新值并查询特定统计信息。
4.游戏开发：处理游戏中角色位置等动态变化的数据。
5.信号处理：在音频或视频编辑中表示信号的变化。
下面解释了差分数组进行区间修改图示方便大家理解~
下面写几个力扣的题目方便大家练习
2848. 与车相交的点
class Solution {
public int numberOfPoints(List<List<Integer>> nums) {
int max=0;
for(List<Integer> p : nums)max = Math.max(max,p.get(1));
int[] diff = new int[max + 2];
for (List<Integer> interval : nums) {
diff[interval.get(0)]++;
diff[interval.get(1) + 1]--;
}
int num=0;
int s=0;
for(int t:diff){
s+=t;
if(s>0)num++;
}
return num;
}
}
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] d=new int[1001];
for(int [] t:trips){
int num = t[0], start = t[1], end = t[2];
d[start]+=num;
d[end]-=num;//不包括end
}
int s=0;
for(int t:d){
s+=t;
if(s>capacity)return false;
}
return true;
}
}
class Solution {
public boolean isCovered(int[][] ranges, int left, int right) {
int[] diff = new int[52];
//对差分数组进行处理
for(int i = 0; i < ranges.length; i++){
diff[ranges[i][0]]++;
diff[ranges[i][1]+1]--;
}
//根据差分数组处理前缀和，为理解方便单独定义sum，可以原地做
int[] sum = new int[52];
for(int i = 1; i <= 51; i++){
sum[i] = sum[i-1] + diff[i];
}
//从left到right判断是否满足sum > 0
for(int i = left; i <= right; i++){
if(sum[i] <= 0) return false;
}
return true;
}
}
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] c = new int[n + 1];
for (int[] bo : bookings) {
int l = bo[0] - 1, r = bo[1] - 1, v = bo[2];
c[l] += v;
c[r + 1] -= v;
}
int[] ans = new int[n];
ans[0] = c[0];
for (int i = 1; i < n; i++) {
ans[i] = ans[i - 1] + c[i];
}
return ans;
}
}
class Solution {
public int minGroups(int[][] intervals) {
int max = intervals[0][1];
for (int[] interval : intervals) {
max = Math.max(max, interval[1]);
}
int[] diff = new int[max + 1];
for (int[] interval : intervals) {
diff[interval[0]] += 1;
if (interval[1] + 1 <= max) {
diff[interval[1] + 1] -= 1;
}
}
int t = 0, ans = 0;
for (int i = 1; i <= max; i++) {
t = t + diff[i];
ans = Math.max(ans, t);
}
return ans;
}
}
class Solution {
public int maxSumRangeQuery(int[] nums, int[][] requests) {
int p = (int)1e9 + 7;
int n = nums.length;
long ans = 0;
int[] diff = new int[n + 1];
Arrays.sort(nums);
for (int i = 0; i < requests.length; i++) {
diff[requests[i][0]]++;
diff[requests[i][1] + 1]--;
}
for (int i = 0; i < n; i++) {
diff[i + 1] += diff[i];
}
Arrays.sort(diff);
for (int i = n; i >= 1 && diff[i] > 0; i--) {
ans += (long)diff[i] * nums[i - 1];
ans %= p;
}
return (int)ans;
}
}
二维差分
2536. 子矩阵元素加 1
class Solution {
public int[][] rangeAddQueries(int n, int[][] queries) {
// 二维差分
int[][] diff = new int[n + 2][n + 2];
for (int[] q : queries) {
int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
diff[r1 + 1][c1 + 1]++;
diff[r1 + 1][c2 + 2]--;
diff[r2 + 2][c1 + 1]--;
diff[r2 + 2][c2 + 2]++;
}
// 计算 diff 的二维前缀和（原地修改），然后填入 ans
int[][] ans = new int[n][n];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1];
ans[i - 1][j - 1] = diff[i][j];
}
}
return ans;
}
}