The introduction

Prefix sum and difference small but beautiful algorithm technique, although rarely used in work, but in some specific scenarios (and interval dependent) can greatly improve program efficiency

The intended purpose

  • Rich programming knowledge

  • Encounter similar scenes can think of the knowledge point, quickly solve the problem

  • Being interviewed or interviewing someone else can come in handy

An interview question

The conventional solution is to simulate the problem. For each booking record, add K in order for the flights involved

Although the calculation method is correct, it is easy to time out. Is there a more efficient solution?

The prefix and

define

You can think of it as the sum of the first n terms of a mathematical sequence

We define the prefix and preSum for an array nums,

Definition of preSum[I] :

preSum[i] = nums[0] + nums[1] + nums[2] +… + nums[i]

Example code to evaluate preSum

Time: O (n)

int[] preSum = new int[m]; for (int i = 1; i<m; i++){ preSum[i] = nums[i] + preSum[i-1]; }Copy the code

use

The prefixes and are mainly suitable for frequently querying the sum of an interval without modifying the original array

For nums[m], if we want to calculate the sum of nums[I…j], we can calculate preSum[j] -presum [i-1]

I don’t have to go over the entire interval

Formula: Interval sum = preSum[J] -presum [i-1]

Is derived:

  • preSum[j] = nums[0] + nums[1] + nums[2] +… + nums [j] — — — — — – (1)

  • preSum[i-1] = nums[0] + nums[1] + nums[2] +… + nums[i-1] ——②

  • preSum[j] – preSum[i-1] = nums[i] + nums[i+1] … + nums [j] — — — — — – (3)

Two-dimensional prefix sum

define

For a two-dimensional array a[m][n] with m rows and N columns

Define prefix and array as s[m][n]

Definition of s[I][J]

A [0][0] is the upper left corner, and a[I][j] is the sum of all elements in the rectangle at the lower right corner

use

If the prefixes and array s have been computed for the original array A, then the sum of the elements in any subrectangle can be computed on the order of O(1)

Suppose we want the sum of all elements in the yellow part of the way, as follows:

  • Add s[x][y] : a[0][0] is the top left corner and a[x][y] is the sum of all elements in the bottom right corner of the rectangle

But just the yellow part, you have to subtract out the green part

  • Subtract s[x][J-1] : the sum of the elements of the left green rectangle

  • Subtract s[i-1][y] : the sum of the elements of the top green rectangle

But you can see that the dark green part has lost an extra piece

  • I need to add s[i-1][J-1]

The summary calculation formula is as follows:

With a [I] [j] to the upper left corner, a [x] [y] for all the elements in the lower right corner of accumulative and = s [x] [y] [x]] [j – 1 – s – s [y] [I – 1] + s [I – 1] [1]

The differential

define

Now we have two arrays of length m

a[m]

b[m]

If B is a prefix and an array of A

So a is the difference array of B

As you can see, prefix sum and difference are a pair of inverse operations

use

The main application of a difference array is to frequently add or subtract elements from an interval of the original array

For example, given an array b[m] of length m, we now need to add k to all elements with subscripts [x~y]

If we use the traversal method, the time is proportional to the length of the interval

But if the difference array A of array B has been computed, the operation can be done on the order of O(1)

The calculation process is as follows:

By definition, a is the difference of B, so B is the prefix sum of A

According to the definition of prefixes and sums

b[x] = a[0] + a[1] + … + a[x]

b[x+1] = a[0] + a[1] + … +a[x] + a[x+1]

.

.

b[y] = a[0] + a[1] + … +a[x] + a[x+1] + … + a[y]

It can be seen that if we add k to a[x], then we add K to b[x] and all subsequent elements

But doing so affects the elements after y and requires that only the elements [x…y] be operated on, so you need to subtract k from a[y + 1]

The summary steps are as follows:

  • a[x] += k

  • a[y+1] -= k

How do I get the end result?

So we’re doing one operation on A, and we’re applying the change to the original array B

You compute a prefix for array A and array B

Two-dimensional finite difference

define

Difference is also available in two dimensions, as defined below

For a two-dimensional array a[m][n] with m rows and N columns

Define prefix and array as b[m][n]

A is the difference array of B by prefix and difference

This is very similar to the two dimensional prefix sum, except that we’re defining the relationship in terms of prefixes and arrays

use

For a two-dimensional array B [m][n] with m rows and n columns, if its difference array A has been calculated, it is possible to add and subtract elements to any subrectangle in B on the order of O(1)

For example, the figure below is the B array, and I want to add k to all the yellow parts in the figure below

If you go through the submatrix in a simulated way, the time it takes is proportional to the number of elements

To clarify a concept:

B [x][y] is equal to the sum of all elements in the rectangle with a[0][0] as the upper-left corner and a[I][j] as the lower-right corner

So when a[x][y] changes, it will affect all elements of the rectangle with B [x][y] as the upper left corner and B [m-1][n-1] as the lower right corner

Perform the following operations:

  1. a[i][j] += k

By definition of prefix and difference, k is added to all parts of array b[I][j] through b[m-1][n-1]

  1. But you don’t have to add k to the green part, so you have to subtract k from all of this

**a[x+1][j] -= k ** : subtract the green part below

**a[j][y+1] -= k ** : minus the green part on the right

  1. It can be seen from the picture that the rectangle b[x+1][y+1] to B [m-1][n-1] is subtracted by k.
  • So we have to add this back

a[x+1][y+1] += k

conclusion

In a two-dimensional difference array, any subrectangle can be added or subtracted with a finite number of computations

Now look at the interview questions

This problem is essentially an application of one-dimensional difference

The following three steps are required to calculate

  • Constructing a difference array

  • Perform bookings. Length for an interval increase

  • Evaluates the target array from the difference array