At the end of the hard problem I met in leetcode week competition, I had no idea when I was doing it, because I had done very little difference, so I didn’t think about difference at all, and then I started to go to prison. So just to summarize the prefixes and difference arrays.
One-dimensional prefix sum
Sum of first intervals
Suppose I have a requirement, and I want to know the sum of some interval in a given one-dimensional array, what do I do?
For example, in an array [1,2,3,4,5,4,3,2,3] of length n, I want to know the sum of the elements in the range from subscripts 2 to 5. The most intuitive way is as follows
public int demo(int[] nums, int l, int r) {
int sum = 0;
for (int i = l; i <= r; i++) {
sum += nums[i];
}
return sum;
}
Copy the codeObviously, there is no better solution, O(n) in time, O(1) in space.
Take the interval sum multiple times
1. Suppose I not only need to find the sum of the interval [2,5], but also [1,3], [4,5]… The sum of, I will give m [l,r], but the array nums is fixed, again, you can still use the above method, you call the demo method every time, but this time complexity is O(n*m), it is easy to timeout.
2. In this case we can use the idea of prefix sum to construct the prefix sum of a one-dimensional array
The original array nums,2,3,4,5,4,3,2,3 [1] the prefix and array sum,3,6,10,15,19,22,24,27 [1]Copy the codeThe construction code is as follows
for (int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
Copy the code3. Now that we have prefixes and arrays, how do we find the sum of ranges between [l,r]?
It is easy to imagine that the sum of the interval [l,r] is (1+2+3+… +r)-(1+2+3+… + l and 1)
For example, if I have array [0,1,2,3,4,5,6,7,8,9,10] and I want the sum of [2,4], I can first find the sum of [0,4], which is 0+1+2+3+4, then I can find the sum of [0,1], which is 0+1+2+3+4, and then I can find the sum of [0,1], which is 0+1+2+3+4. Is it just the sum of the interval [2,4]?
Sum [l,r] = sum[r] -sum [l -1]
Two-dimensional prefix sum
Similar to the one-dimensional prefix sum, if you take the sum of the range within the interval many times, you can use the idea of the two-dimensional prefix sum, so what is the interval of the two-dimensional array? If the red matrix has [I,j] in the upper left corner and [m,n] in the lower right corner, it is possible to circle the matrix with these two coordinates
Sum of first intervals
Now, is it easy to figure out the sum of my red matrix, just walk through it
public int demo(int[][] matrix, int i, int j, int m, int n) {
int sum = 0;
for (int k = i; k <= m; k++) {
for (intl = j; l <= n; l++) { sum += matrix[k][l]; }}return sum;
}
Copy the codeTake the interval sum multiple times
What if I want to do it multiple times? So it’s going to be slow every time, but is there a line of code that can solve this, of course there is, we can construct the sum of the two dimensional prefixes, and then using the two dimensional prefixes and the array, we can figure out the sum of the intervals in one line of code
1, we first construct two-dimensional prefix and array, using the following code can be
public int[][] demo(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] sum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + matrix[i - 1][j - 1] - sum[i - 1][j - 1]; }}return sum;
}
Copy the codeHow to understand? If I want the sum from the top left to the red circle, is that equal to the sum of the two green matrices plus the value of the red circle, minus the overlap of the green matrices?
The prefixes and arrays are as follows
This row of zeros is mainly to prevent the subscript from crossing the boundary, which would be time-consuming and unelegant to do special judgment
[I,j]-[m,n] [I,j]-[m,n] [I,j]-[m,n]
So let’s say I want to know the sum of the red matrix, which is essentially the sum of the green matrix minus the sum of the two blue matrices plus the sum of the overlapping blue matrices as follows
/** * sum is a prefix and an array, ranging from [I,j] to [m,n]. The subscript of ijmn is the subscript of the original array */
public int getSum(int[][] sum, int i, int j, int m, int n) {
i += 1;
j += 1;
m += 1;
n += 1;
return sum[m][n] - sum[m][j - 1] - sum[i - 1][n] + sum[i - 1][j - 1];
}
Copy the codeA one-dimensional finite difference
What is a difference array? I personally think it is more difficult to understand than prefix and. First of all, let’s find a scenario to understand when a difference array is used, such as the problem 1109 of force button. Flight booking statistics
The first interval plus x
[1,2,10] / n=5 [0,0,0,0] / Int I = 1; i <= 2; i++) nums[i] += 10; This gives us [0,10,10,0,0] but these numbers can be quite large in length. Is there a way to quickly add x to all numbers in a range for what we call a difference
All of the multiple intervals plus x
Diff [I] = nums[I] -nums [i-1]
For example, the original array [1,10,10,1,1] is constructed according to the definition of the difference array is [1,9,0,-9,0], powerful is based on the difference array can be derived from the original array, the difference array prefix and array is the original array, readers can try to push, this must be understood.
So now I want to add 20 to the difference array [0,10,0,-10,0], to the interval [2,3], how do I write it, 20 to 2, 10 to 2, and then when I take the prefix sum, everything >=2 will be added to 20, but we need to stop at 3, Student: Can I go to minus 20 at 4, so that when I take the prefix sum, I don’t have to worry about numbers greater than 3.
It is easy to write the answer to the above question by following the steps above
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n];
for (int[] booking : bookings) {
diff[booking[0] - 1] += booking[2];
if(booking[1] < n) diff[booking[1]] -= booking[2];
}
// The difference array is prefixed and -> the original array
for (int i = 1; i < n; i++) {
diff[i] += diff[i - 1];
}
return diff;
}
Copy the codeTwo-dimensional finite difference
1. How to understand two-dimensional difference array? Let’s say I now have a matrix, a two-dimensional difference array
If I make the difference array look like this
So if you take the prefix and the array of this difference array you get
Obviously, if we are a number of difference array, add 1, beg the prefix and array, found that it will affect the current coordinates, to the lower right corner of the matrix, let whole matrix is 1, so if we can guess, want a two-dimensional matrix of all of the whole add and subtract X, with difference array is not only need to change a few Numbers.
2. If I want to increase the red matrix by 1, how should I change the difference array?
If I make the difference array look like this
So that’s what happens when you take the prefix and you get the original array
We’re going to find that it’s a little bit different from the original array that we want, and the original array that we want is to add four ones to the red, and zeros to the rest of the red, which is to say, we’re not going to add anything beyond the red matrix, if we make the difference fraction fabric look like this
So that gives us the prefix and the array
Found after we changed two – 1, prefix and when there will be overlapping reduce part, this part is the lower right corner of the red circle to the matrix added to reduce the overall 1, we talked about just now, for a matrix to the lower right corner of the overall 1, is to make the difference in array, red circle number plus 1, then calculate the prefix and arrays, So when we construct the difference array, we need to change the position of the red circle. The final difference array is as follows. Using this difference array to solve the prefix and array, we can get the result that the red matrix is all 1’s.
General solution is as follows
To add x to the matrix [I,j] through [m,n], we should do the following for the difference array
Diff [I][j] += x diff[m + 1][j] -= x, diff[I][n + 1] -= x Diff [m+1][n +1] += x (diff[m +1,n+1] += x)Copy the codeIf we add and subtract x multiple times, all we have to do is figure out the prefix and the array of the difference array, and we’ll get the final result.
Practical problem
Can search for some prefix and difference mid questions, if skilled can do the following questions
Cover the grid with stamps
First, we need to paste the stamp, we will traverse the two-dimensional array grid, determine whether the point is beyond the grid (this can be placed in the for loop to determine whether there is an obstacle [x], how to determine whether the position I want to paste now has an obstacle [x]?
1. We need to construct a prefix and array for grid. According to this array, we can quickly know whether there are obstacles in a matrix, that is, whether the sum of this interval is 0, if it is 0, there are no obstacles.
2. If there are no obstacles, that is, stamps can be affixed, then we should use the difference array to quickly add the whole interval to +1.
If there is a 0 in the prefix and array, and the point in the grid is not [x], then there is a place that is not pasted.
public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
int m = grid.length;
int n = grid[0].length;
// Why m+1, n+1 Because you don't have to make a special judgment to find a prefix sum
int[][] sum = new int[m + 1][n + 1];
// Why m+2, n+2 Because you're going to need the previous digit to get the prefix sum
[I,j] to [m,n] add x to the whole. To avoid arrays out of bounds and special judgment, use m+2,n+2
int[][] diff = new int[m + 2][n + 2];
// Build prefixes and arrays to quickly determine whether the matrix contains [x]
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + grid[i - 1][j - 1] - sum[i - 1][j - 1]; }}for (int i = 1; i + stampHeight - 1 <= m; i++) {
for (int j = 1; j + stampWidth - 1 <= n; j++) {
int p = i + stampHeight - 1;
int q = j + stampWidth - 1;
[p, q] [X] [p, q]
int x = sum[p][q] + sum[i - 1][j - 1] - sum[p][j - 1] - sum[i - 1][q];
// If there is no [x], [I,j] to [p,q], the whole matrix +1
if (x == 0) {
diff[i][j] += 1;
diff[p + 1][j] -= 1;
diff[i][q + 1] - =1;
diff[p + 1][q + 1] + =1; }}}// Difference arrays are converted to prefixes and arrays
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
diff[i][j] = diff[i - 1][j] + diff[i][j - 1] + diff[i][j] - diff[i - 1][j - 1]; }}// When all the stamps are pasted, check if there are any squares missing
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (diff[i][j] == 0 && grid[i - 1][j - 1] = =0) return false; }}return true;
}
Copy the code