The difference is used in combination with prefix and. It is applied to the case where the interval is modified and only queried once.
One dimensional difference
For \ ([a_1, a_2, a_3,..., a_n] \), prefix and \ (s_i = a_1 + a_2 +,..., a_i \), difference \ (diff_0 = a_0-0, \ diff_i = a_i - a {I-1} \)
So \ (a_i = 0 + diff_0 + diff_1 +... + diff_i \)
Adding \ (a[i...j] \) to \ (val \) can be directly converted to adding \ (diff[i] += val, \ diff[j+1] -= val \) from front to back to get the modified \ (a_i \)
LC 1094. carpooling
trips[i] guests get on from trip[1] and get off from trip[2] to judge whether the capacity will be exceeded on the bus
Method: equivalent to interval modification, set [trip[1], trip[2]-1] += val
class Solution {
public:
void update(vector<int>& diff, int l, int r, int val) {
diff[l] += val;
diff[r+1] -= val;
}
bool carPooling(vector<vector<int>>& trips, int capacity) {
const int maxn = 1000+5;
vector<int>diff(maxn, 0);
for(auto& trip : trips) {
update(diff, trip[1], trip[2]-1, trip[0]);
}
int cur = 0;
for(int i = 0;i < maxn;i++) {
cur += diff[i];
if(cur > capacity) return false;
}
return true;
}
};
LC1109. Flight reservation statistics
Method: the difference template problem, pay attention to the space to open \ (n+2 \)
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int>diff(n+2, 0); // With [1...n], the difference needs one more
for(auto& book : bookings) {
diff[book[0]] += book[2];
diff[book[1]+1] -= book[2];
}
int cur = 0;
vector<int>ans;
for(int i = 1;i <= n;i++) {
cur += diff[i];
ans.push_back(cur);
}
return ans;
}
};
LC 1893. Check that all integers in the region are overwritten
Method: template question
class Solution {
public:
bool isCovered(vector<vector<int>>& ranges, int left, int right) {
vector<int>diff(55, 0);
for(auto& ran : ranges) {
diff[ran[0]] += 1;
diff[ran[1]+1] -= 1;
}
int cur = 0;
for(int i = 1;i <= right;i++) {
cur += diff[i];
if(i >= left && cur == 0) return false;
}
return true;
}
};
LC1854. The most populous year
Question meaning: similar to the question of bus, ask for the year with the largest number of people
Method: it is equivalent that everyone has an action interval, which is transformed into interval modification (remember this idea)
class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
vector<int>diff(2050+2, 0);
for(auto& log : logs) {
diff[log[0]] += 1;
diff[log[1]] -= 1;
}
int cur = 0, mymax = 0, year;
for(int i = 1950;i <= 2050;i++) {
cur += diff[i];
if(cur > mymax) {
mymax = cur;
year = i;
}
}
return year;
}
};
LC732. My schedule III
Question meaning: similar to the bus, find the maximum number of overlaps at a certain time
Method: it is still differential, but the time span is very large. It is necessary to use map to store discrete points. When accumulating, it is still necessary to accumulate in order.
class MyCalendarThree {
public:
map<int, int>mp; // Unordered cannot be used_ map
MyCalendarThree() {
}
int book(int start, int end) {
mp[start] += 1;
mp[end] -= 1;
int cur = 0, mymax = 0;
for(auto it = mp.begin();it != mp.end();it++) {
cur += it->second;
if(cur > mymax) mymax = cur;
}
return mymax;
}
};
Finally, a little hidden, hard
LC 1674. Minimum number of operations to make arrays complementary
Given an array with an even length, find the minimum number of operations such that num [i] + num [n - 1 - I] are equal to the same number, and each element after modification is required to be between 1 and limit.
method:
Method 1: violence, enumeration and, easy to know, between 1~2*limit. For the specified sum, it may be modified 0 times, 1 times, 2 times.
class Solution {
public:
int myMinMoves(vector<int>& nums, int k, int limit) {
int n = nums.size();
int res = 0;
for(int i = 0;i < n/2;i++) {
int a = nums[i], b = nums[n-1-i];
if(a+b == k) continue;
if(a >= k && b >= k) res+=2; // Two big
else if(a >= k && b < k) res+=1; // One big and one small
else if(b >=k && a < k) res+=1;
else if(max(a,b)+limit >= k) res +=1; // Two small
else res += 2;
}
return res;
}
int minMoves(vector<int>& nums, int limit) {
int ans = 2*nums.size();
for(int i = 1;i <= 2*limit;i++) {
ans = min(ans, myMinMoves(nums, i, limit));
}
return ans;
}
};
The judgment conditions can be simplified as follows:
int myMinMoves(vector<int>& nums, int k, int limit) {
int n = nums.size();
int res = 0;
for(int i = 0;i < n/2;i++) {
int a = min(nums[i], nums[n-1-i]);
int b = max(nums[i], nums[n-1-i]);
if(a+b == k) continue;
else if(a < k && k <= b+limit) res += 1;
else res += 2;
}
return res;
}
Method 2: using the idea of interval modification, we can optimize based on the simplified version above. For a given [a, b], its contribution includes adding 1 to the interval [a+1, b+limit], keeping [a+b, a+b] unchanged, and adding 2 to the others.
If the difference is used, it should be equivalent to [2, 2*limit] += 2, [a+1, b+limit] -= 1, [a+b, a+b] -=1
class Solution {
public:
// https://leetcode-cn.com/problems/minimum-moves-to-make-array-complementary/solution/jie-zhe-ge-wen-ti-xue-xi-yi-xia-chai-fen-shu-zu-on/
// Just change the endpoint, because the difference in the middle is still 0, unchanged
// Interval modification, too lazy to write segment tree (only interval modification, single point query)
// dp[i] represents the minimum number of operations when the sum is 1
// dp[i] = diff[0]+diff[1]+diff[2]...+diff[i]
void update(vector<int>& diff, int l, int r, int val) {
diff[l] += val;
diff[r+1] -= val;
}
int minMoves(vector<int>& nums, int limit) {
int n = nums.size();
vector<int>diff(2*limit+2, 0);
for(int i=0, j=n-1; i<j; i++,j--) {
int a = min(nums[i], nums[j]);
int b = max(nums[i], nums[j]);
update(diff, 2, 2*limit, 2);
update(diff, a+1, b+limit, -1);
update(diff, a+b, a+b, -1);
}
int ans = n, sum=0;
for(int i = 2;i <= 2*limit;i++) {
sum += diff[i];
if(sum < ans) ans = sum;
}
return ans;
}
};
Note: in the above examples, the initial value of the diff array is 0. If the problem needs to consider the original array, add the original value or modify the initialization of diff when accumulating
Two dimensional difference
Reference link: