Hello everyone, I am Negative Xueming Candle.

“Golden Nine silver ten” autumn recruitment season has begun, I believe many students are already in the resume, interview. The algorithm question is the interview must test point, how in the shortest time, master the most practical algorithm knowledge? I am writing a series of articles on this official account: “Autumn recruitment will be able to algorithm”, this series of efforts to use the most easy-to-understand language, explain the most common autumn recruitment, will be able to algorithm knowledge, so that everyone can get the maximum return on investment time.

For subsequent articles, please pay attention to our official account “Negative Xueming Candle”.

Today’s lesson is “prefix and”, which is a common interview test and a very easy to learn algorithmic skills. It only takes you 15 minutes to read this article, and you’ll be able to beat all the “prefixes and” questions that come your way.

Start with the dynamic sum of one-dimensional arrays

The prefix and the preSum, it’s a horrible name, but it’s a piece of paper.

To get some background, let’s look at a simple question from LeetCode:1480. Dynamic sum of one-dimensional arrays.So let’s do this oneRunningSum [I] = sum (nums [0]... nums[i])If you’re not familiar with prefix and, you might write a double loop: eachrunningSum[i]And accumulation from
$0$Location to
$i$The location of thenums[i]. That is, write the following code:

vector<int> runningSum(vector<int>& nums) {
    const int N = nums.size(a);vector<int> preSum(N, 0);
    for (int i = 0; i < N; ++i) {
        int sum = 0;
        for (int j = 0; j <= i; ++j) {
            sum += nums[j];
        }
        preSum[i] = sum;
    }
    return preSum;
}
Copy the code

The time complexity of the double cycle is O(N2)O(N^2)O(N2), which is relatively inefficient.

In fact, as long as we change our thinking slightly, we find that there is no need to use a double cycle.

RunningSum [I] = sum(nums[0]… Nums [I]), runningSum[I + 1] = sum(nums[0]… Nums [I]) + nums[I + 1] = runningSum[I] + nums[I + 1].

It is this simple transformation that allows us to eliminate the inner loop. The code is as follows:

vector<int> runningSum(vector<int>& nums) {
    const int N = nums.size(a);vector<int> preSum(N, 0);
    for (int i = 0; i < N; ++i) {
        if (i == 0) {
            preSum[i] = nums[i];
        } else {
            preSum[i] = preSum[i - 1] + nums[i]; }}return preSum;
}
Copy the code

What are “prefix and”

​

If you understand the above, the preSum array is just a “prefix sum”! It’s that simple!

The prefix sum is the sum of nums from position 0 to position iii, and is stored in preSum as preSum[I].

PreSum [I] = preSum[I – 1] + nums[I]; preSum[I – 1] = preSum[I – 1] + nums[I] PreSum [I] = nums[I]

In other common writing, to avoid this if judgment, we often define the length of preSum as the length of the original array + 1. The 0th position of preSum, which acts as a placeholder, is set to 0. PreSum [I] = preSum[i-1] + nums[i-1], where preSum[I] represents the sum of all elements to the left of element iii in numS (excluding the current element iii).

The following to[1, 12, -5, -6, 50, 3]For example, how to solve it with a GIFpreSum.The figure above shows:

• preSum[0] = 0;
• preSum[1] = preSum[0] + nums[0];
• preSum[2] = preSum[1] + nums[1];
• .

What’s the use of prefix and

Use a: before the array
$i$The sum of the number

Finding the sum of three numbers in front of an array is the definition of a prefix and array, so it is the most basic usage. For example:

• If requirednumsThe sum of the first two numbers in the array (i.e
  $sum(nums[0], nums[1])$), return directly
  $preSum[2]$Can.
• Similarly, if you want tonumsThe sum of all elements in an array (i.e
  $sum(nums[0].. nums[length – 1])$), return directly
  $preSum[length]$Can.

​

Purpose two: to find the array interval sum

Using the preSum array, the sum of all elements in any numS interval [I,j][I,j][I,j] (both ends are included) can be quickly solved in O(1)O(1)O(1) O(1).

Sum (I,j)=preSum[j+1]−preSum[I]sum(I,j)=preSum[j+1] -presum [I]sum(I,j)=preSum[j+1]−preSum[I]

How does that work? It’s just eliminating the common sum from 0 to I minus 1, and you get the sum from I to j.

Note that preSum[j + 1] and preSum[I] are used in the formula above, and you need to understand why. (If you can’t understand the knowledge, you can’t remember, so be sure to understand)

• preSum[j + 1]Represents thenumsIn the array
  $[0, j]$The sum of all the digits of
  $0$ 和
  $j$).
• preSum[i]Represents thenumsIn the array
  $[0, i – 1]$The sum of all the digits of
  $0$ 和
  $i – 1$).
• When you subtract the two, the result staysnumsIn the array
  $[i, j]$Sum of all the numbers of.

“Prefix sum” example

Now that we know what “prefix and” are and what they do, let’s practice a simple example. The problem is 303. Fields and retrievals – Arrays are immutable. SumRange (I, j), sumRange(I, j), sumRange(I, j), sumRange(I, j), sumRange(I, j)

See here, I believe we already know, direct use of “prefix and” not seconds to kill it!

Next, I’ll post the code for the three languages.

1. Python

class NumArray:

    def __init__(self, nums: List[int]) :
        N = len(nums)
        self.preSum = [0] * (N + 1)
        for i in range(N):
            self.preSum[i + 1] = self.preSum[i] + nums[i]

    def sumRange(self, i: int, j: int) - >int:
        return self.preSum[j + 1] - self.preSum[i]
Copy the code

2. C++

class NumArray {
public:
    NumArray(vector<int>& nums) {
        const int N = nums.size(a); preSum.resize(N + 1);
        for (int i = 0; i < N; ++i) {
            preSum[i + 1] = preSum[i] + nums[i]; }}int sumRange(int i, int j) {
        return preSum[j + 1] - preSum[i];
    }
private:
    vector<int> preSum;
};
Copy the code

3. Java

class NumArray {
    private int[] preSum;
    public NumArray(int[] nums) {
        final int N = nums.length;
        preSum = new int[N + 1];
        for (int i = 0; i < N; ++i) {
            preSum[i + 1] = preSum[i] + nums[i]; }}public int sumRange(int i, int j) {
        return preSum[j + 1] - preSum[i]; }}Copy the code

Complexity analysis

• Space complexity: defining the “prefix and” array requires N+1N +1N +1 space, so the space complexity is O(N)O(N)O(N);
• Time complexity:
  • Initialize “prefix and” array, need to traversal the array once, the time complexity is O(N)O(N)O(N);
  • o
    $[i, j]$The interval sum in the scope is accessed onlypreSum[j + 1] 和 preSum[i], the time complexity is
    $O(1)$.

​

expand

Extension 1: Hidden “prefixes and”

Algorithm problems are like many leaves growing on a big tree, although each leaf is different, but they all have a common trunk. Algorithm topic knowledge is limited, there are a large number of problems are the same solution batch of different skin. We take the643. Maximum mean of subarray IFor example, this problem asks for an arraynumsWhere all lengths arekThe average of the largest continuous subarray of.This question can be used as:The prefix andYou can also use a fixed size k.The sliding window“To solve.

To find the maximum mean in the window of size K, we can find the maximum “sum” of [I, I +k][I, I +k][I, I +k] and divide by k, i.e. (preSum[I +k] -presum [I])/k.

In general, if the problem requires interval sums, then you can consider using prefix sums.

Extension 2: “Prefix sum” of Two-dimensional Matrices

Another extension is to find the “prefix sum” of a two-dimensional matrix. Such as the first304. Two dimensional region and retrieval – Matrix immutable.When the “prefix sum” extends to the two-dimensional interval, the following ideas can be used to solve it.

Step 1: Find preSum

​

We define preSum[I][j] to represent the sum of all elements of the subrectangle from [0,0] to [I,j].

If the recursive formula of preSum[I][j] is:

PreSum [I] [j] = preSum [I – 1) [j] + preSum [j – 1] – [I] preSum [I – 1) + matrix [j – 1] [I] [j] preSum [I] [j] = preSum [j] + [I – 1] preSum [I] [j – [1] – preSum [I – 1]] j – 1 + matrix [I] [j] preSum [I] [j] = preSum [I – 1) [j] + preSum [j – 1] – [I] preSum [I – 1) + matrix [j – 1] [I] [j].

To help understand:

S (O, D) = S (O, C) + S (O, B) – (A) O, S + DS (O, D) = S (O, C) + S (O, B) – (A) O, S + DS (O, D) = S (O, C) + S (O, B) – (A) O, S + D

Minus the
$S(O, A)$The reason is that
$S(O, C)$ 和
$S(O, B)$There are
$S(O, A)$, namely added twice
$S(O, A)$So we have to subtract once
$S(O, A)$.

Step 2: Calculate the area of subrectangle according to preSum

We found preSum from [0,0] to [I,j].

If the area of subrectangles from [row1, col1] to [Row2, col2] is calculated using preSum, the following recursion formula is used:

PreSum [row2] [col2] – preSum [row2] [col1-1] – preSum [row1-1] [col2] + preSum [row1-1] [col1-1] preSum [col2] – [row2] preSum[row2][col1 – 1] – preSum[row1 – 1][col2] + preSum[row1 – 1][col1 – 1] preSum [row2] [col2] – preSum [row2] [col1-1] – preSum [row1-1] [col2] + preSum [row1-1] [col1-1)

Again, use a graph to illustrate:

S (A, D) = S (O, D) – S (O, E) – S (O, F) + S (O, G) S (A, D) = S (O, D) – S (O, E) – S (O, F) + S (O, G) S (A, D) = S (O, D) – S (O, E) – S (O, F) + S (O, G)

Plus subrectangles
$S(O, G)$The reason for the area is that
$S(O, E)$ 和
$S(O, F)$There are
$S(O, G)$That is, minus twice
$S(O, G)$So I have to add it once
$S(O, G)$.

Once this principle is understood, the problem is not difficult to solve.

conclusion

​

1. The prefix sum principle is very simple, but very useful, and you can’t avoid it when dealing with interval sum problems.
2. The “prefix sum” is calculated by preprocessing the array and obtaining the “sum” from position 000 to position iii.
3. The prefix sum is a quick way to find an arraynumsSpecified interval of
   $[i, j]$The sum of all elements in.
4. The complexity of prefix sum:
   1. The space complexity is O(N)O(N)O(N);
   2. The initialization time is O(N)O(N)O(N);
   3. The sum of intervals is O(1)O(1)O(1).

​

This article is the first of a series of articles on the algorithm of autumn recruitment, and I hope it will be helpful.

Your support is my motivation to continue writing! Ask for likes, ask for attention, ask for retweets. See you next time!