Prefix and difference

The prefix and

1. What are prefix and

This is just one-dimensional prefix sums and two-dimensional prefix sums

That is, assuming a sequence {an} {a_n \} {an}, so the prefix and can be understood as a1, a2 and a3 +… +aia_1 + a_2 + a_3 + … + a_ia1+a2+a3+… + ai. Prefixes and arrays are arrays that store prefixes and sums starting with a1a_1A1 and ending with aiA_iai.

Here’s an example:

if

$b_1 = a_1$

$b_2 = a_1 + a_2$

$b_3 = a_1 + a_2 + a_3$

$.$

$b_n = a_1 + a_2 + a_3 + … + a_n$

You can get

$b_1 = a_1$

$b_2 = b_1 + a_2$

$b_3 = b_2+ a_3$

$.$

$b_n = b_{n-1}+ a_n$

the
$\{b_n\}$for
$\{a_n\}$Prefix and array of.

2. Why prefix and? What does prefix and sum do?

Prefix sum is an important preprocessing, which can greatly reduce the time complexity of query. Why?

Here’s an example:

Suppose we need to compute the sum of a1a_1a1 to ana_nan, and we usually do that by using a for loop. What if I want to change my demand, and I want to take the sum of a7a_7a7 to ana_nan? That still requires another for loop, so I need to compute a4a_4A4 ~ an−4a_{n-4}an−4. If we had n of these requirements, we would have to write n cycles, and the time complexity would be high.

Conclusion:

So we take the sum of a1a_1A1 through aiA_iai and store it in an array B, using the prefix sum, a for loop.

If the sum of ala_lal ~ ara_rar is required, the sum of ala_lal ~ ara_rar can be obtained by using b[r]−b[L −1]b[r] -b [L-1]b[r]−b[L −1] The time complexity of this computation operation is O(1)O(1)O(1).

Proof:

$b[r] = a[1] + a[2] + … + a[l-1] + a[l] + a[l+1] + … + a[r]$

$b[l-1] = a[1] + a[2] + … + a[l-1]$

so
$b[r] – b[l-1] = a[l] + … + a[r]$

3. Two-dimensional prefix sum

So we’ve been talking about one-dimensional prefixes and sums, and you probably don’t feel that much of an efficiency gain, but when you go to two-dimensional arrays, you can imagine for yourself how slow it is to not have prefixes and processing.

Two-dimensional prefixes and sums are a little harder to understand, but it’s important to figure out what prefixes and arrays store.

If there is a two-dimensional array anma_{nm}anm as follows

$\left[ \begin{matrix} a_{11} &a_{12} &a_{13} &a_{14}\\a_{21} &a_{22} &a_{23} &a_{24}\\a_{31} &a_{32} &a_{33} &a_{34}\\a_{41} &a_{42} &a_{43} &a_{44}\end{matrix} \right]$

So what does anma_{nm}anm prefix and array mean? Remember bnmb_{nm} BNM as the prefix and array of anma_{nm}anm.

the
$b[i][j]$Is represented by
$a[1][1]$Is the upper left corner, with
$a[i][j]$Is the rectangle in the lower right corner, the sum of all elements in the rectangle.

For example

B [2][3]b[2][3]b[2][3] is the sum of all the following elements

$\left[\begin{matrix}a_{11} &a_{12} &a_{13}\\a_{21} &a_{22} &a_{23} \end{matrix}\right]$

A similar

B [4][2]b[4][2]b[4][2] is the sum of all the following elements

$\left[\begin{matrix} a_{11} &a_{12} \\a_{21} &a_{22} \\ a_{31} &a_{32}\\ a_{41} &a_{42}\end{matrix}\right]$

conclusion

If we ask
$a[x_1][y_1]$Is the upper left corner,
$a[x_2][y_2]$Is the sum of all elements in the lower right corner of the rectangle,

namely
$B [x_2] [y_2] [x_2] [] y_1-1 – b – b [x_1-1] [y_2] [x_1-1) + b (y_1-1).$

So you just have to draw your own graph to prove it, but it’s relatively easy. And it’s easy to remember, subtracting everything by one.

The differential

1. What is difference

You can think of it as the inverse of the prefix sum. How to understand? Let’s just look at an example.

Let there be a difference array {an}\{a_n\}{an}, whose prefix and array are {bn}\{b_n\}{bn}

Then the difference array

$a_1 = b_1$

$a_2 = b_2 – b_1$

$a_3 = b_3 – b_2$

$.$

$a_n = b_n – b_{n-1}$

And prefixes and arrays

$b_1 = a_1$

$b_2 = a_1 + a_2$

$b_3 = a_1 + a_2 + a_3$

$.$

$b_n = a_1 + a_2 + … + a_n$

So that makes sense. Make sure you understand the prefix and the difference.

2. Difference

Add a number to an interval of a sequence. For example, I want to add CCC to each element in the segment a1a_1A1 ~ an−5a_{n-5}an−5. Don’t think about using multiple loops.

3. The use of difference

For a one-dimensional difference, to add a number CCC to {l,r}\{l,r\}{l,r} {l,r} {l,r}, we need only

$a[l] += c$

$a[r+1] -= c$

Can.

Proof: we must understand the difference array plus a number, the effect on the prefix and array!

Suppose a1a_1A1 plus CCC, then the prefix and array {bn}\{b_n\}{bn} become the following

$b_1 = a_1 + c$

$b_2 = a_1 + c + a_2$

$b_3 = a_1 + c + a_2 + a_3$

$.$

$b_n = a_1 + c + a_2 + … + a_n$

B1b_1b1 ~ bnb_nbn plus CCC, what if a2a_2a2 minus CCC?

$b_1 = a_1 + c$

$b_2 = a_1 + c + a_2 – c = a_1 + a_2$

$b_3 = a_1 + c + a_2 – c + a_3 = a_1 + a_2 + a_3$

$.$

$b_n = a_1 + a_2 + … + a_n$

The final result is just B1b_1b1 plus CCC. More examples can be tested by the reader to enhance the impression.

If so,
$a_i$I added a number
$c$, then the corresponding prefix and array
$b_i$And everything after that is going to be added
$c$, similarly, if
$a_j$Minus a number
$c$, then the corresponding prefix and array
$b_j$And everything after that is subtracted
$c$ 。

4. Two-dimensional difference

Now that we have the basis for one-dimensional difference, let’s look at two-dimensional difference. The first thing to remember is the meaning of the two dimensional prefix sum, which is key to understanding two dimensional difference.

As follows, there is a difference array {a44} \ {a_ {44} \} {a44} and its corresponding prefix and array for {b44} \ {b_ {44} \} {b44}, namely

[a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44]\left[ \begin{matrix} a_{11} &a_{12} &a_{13} &a_{14}\\a_{21} &a_{22} &a_{23} &a_{24}\\a_{31} &a_{32} &a_{33} &a_{34}\\a_{41} &a_{42} &a_{43} &a_{44}\end{matrix} \ right] ⎣ ⎢ ⎢ ⎢ ⎡ a11a21a31a41a12a22a32a42a13a23a33a43a14a24a34a44 ⎦ ⎥ ⎥ ⎥ ⎤ and [b11b12b13b14b21b22b23b24b31b32b33b34b41b42b43b44]\left[ \begin{matrix} b_{11} &b_{12} &b_{13} &b_{14}\\b_{21} &b_{22} &b_{23} &b_{24}\\b_{31} &b_{32} &b_{33} &b_{34}\\b_{41} &b_{42} &b_{43} &b_{44}\end{matrix} \ right] ⎣ ⎢ ⎢ ⎢ ⎡ b11b21b31b41b12b22b32b42b13b23b33b43b14b24b34b44 ⎦ ⎥ ⎥ ⎥ ⎤

If a22a_{22}a22 is added with a number CCC, what happens to the prefix and array? The answer is as follows

$\left[ \begin{matrix} b_{11} &b_{12} &b_{13} &b_{14}\\b_{21} &b_{22} + c &b_{23} + c &b_{24} + c\\b_{31} &b_{32} + c &b_{33} + c &b_{34} + c\\b_{41} &b_{42} + c &b_{43} + c &b_{44} + c\end{matrix} \right]$

So a24a_{24}a24 minus a number CCC, so

$\left[ \begin{matrix} b_{11} &b_{12} &b_{13} &b_{14}\\b_{21} &b_{22} + c &b_{23} + c &b_{24} \\b_{31} &b_{32} + c &b_{33} + c &b_{34}\\b_{41} &b_{42} + c &b_{43} + c &b_{44}\end{matrix} \right]$

A42a_ {42}a42 minus a number CCC, so

$\left[ \begin{matrix} b_{11} &b_{12} &b_{13} &b_{14}\\b_{21} &b_{22} + c &b_{23} + c &b_{24} \\b_{31} &b_{32} + c &b_{33} + c &b_{34}\\b_{41} &b_{42} &b_{43} &b_{44} – c\end{matrix} \right]$

And then finally a44a_{44}a44 plus a number CCC

$\left[ \begin{matrix} b_{11} &b_{12} &b_{13} &b_{14}\\b_{21} &b_{22} + c &b_{23} + c &b_{24} \\b_{31} &b_{32} + c &b_{33} + c &b_{34}\\b_{41} &b_{42} &b_{43} &b_{44}\end{matrix} \right]$

And the difference array is now zero

$\left[ \begin{matrix} a_{11} &a_{12} &a_{13} &a_{14}\\a_{21} &a_{22} + c &a_{23} &a_{24} – c\\a_{31} &a_{32} &a_{33} &a_{34}\\a_{41} &a_{42} – c &a_{43} &a_{44} + c\end{matrix} \right]$

So we can see that if we want to add a number CCC to all the elements in the small rectangle ax1y1a_{x_1y_1}ax1y1 as the upper left corner and ax2y2a_{x_2y_2}ax2y2 as the lower right corner, we need

$a[x_1][y_1] += c$

$a[x_1][y_2+1] -= c$

$a[x_2+1][y_1] -= c$

$a[x_2+1][y_2+1] += c$

For more Java content, please follow my official account ACJavaBear, where I will post the first time. Let’s learn Java