Introduction to algorithms in java-cumulative sum

Article summary

This is a series of articles that I have compiled in my study and memo. The fifth. Click here for previous articles.

In this article

-** Cumulative sum **

I will study about. Let's finish the exploration and study another algorithm (what you were interested in in the weekly contest).

Cumulative sum

It seems to be a calculation technique. It seems to be convenient to find the sum of the sections with an array.

Reference: Be able to write the cumulative sum without thinking!

I will explain it for the time being.

Array a, {1,3,1,4,7,6,1,0,9} Shall we say that? For example, suppose you are asked to find the sum of the 3rd to 5th of this array.

Normal method

a: Simply add the 3rd to 5th of {1,3, ** 1,4,7 **, 6,1,0,9}. The answer is 1 + 4 + 7 = 12

Use cumulative sum

In addition to a, create an array b that stores the sum up to the i-th of a. b：{0,1,4,5,9,16,22,23,23,32} If you write a_1 like the first element of a, b_1 = 0 (fixed here. Subscripts will be shifted by one thereafter) b_2 = a_1 = 1 b_3 = a_1 + a_2 = 1 + 3 = 4 b_4 = a_1 + a_2 + a_3 = 1 + 3 + 1 = 5 b_5 = a_1 + ... + a_4 = 1 + ... + 4 = 9 b_6 = a_1 + ... + a_5 = 1 + ... + 7 = 16 ...

I feel said. At this time, the sum of the 3rd to 5th of a is calculated as follows. b_6 - b_3 = 16 - 4 = 12

The details are as follows.

  b_6 = a_1 + a_2 + a_3 + a_4 + a_5
-)b_3 = a_1 + a_2
--------------------------------------
      = a_3 + a_4 + a_5

Do you understand somehow? By saving the sum in order from the front, you don't have to do the addition of 3rd + 4th + 5th!

What are you happy about?

For example, when you have to find the sum from the ● th to the ▲ th many times (assuming a problem with many variations of ● and ▲), you need to turn the loop over and over again in the usual way. There is, but if you use the cumulative sum, you can find the sum in one shot (O (1)).

Let's look at the problem.

example

Example: AtCoder --abc037-c "sum"

N K
a1 .. aN

This is the problem. It's just a matter of cumulative sum. You have to add K pieces N-K + 1 times. The amount of calculation is O (K * (N-K + 1)). In addition, you can see that if you choose poorly (K = N / 2, etc.), it will cost O (N ^ 2). This is not in time. That's why the cumulative sum comes into play. "K additions are N-K + 1 times", but if you use the cumulative sum, "K additions" can all be done with O (1), so the amount of calculation is roughly O (N). ..

The policy is as follows.

--Prepare an array to hold the cumulative sum --The sum of each of 1 ~ K, 2 ~ K + 1,3 ~ K + 2, ..., N-K + 1 ~ N is calculated by the array of cumulative sums, and finally the sum is the answer.

Then, the following is an example of the answer.

Main.java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		long a[] = new long[n]; //Array to receive input
		long b[] = new long[n + 1]; //Store cumulative sum

		for (int i = 0; i < n; i++) {
			//Receive input
			a[i] = sc.nextLong();
		}

		for (int i = 1; i <= n; i++) {
			//Cumulative sum calculation
			b[i] = b[i - 1] + a[i - 1];
		}

		long ans = 0; //Answer storage
		for (int i = 0; i < n - k + 1; i++) {
			ans += b[i + k] - b[i];
		}

		System.out.println(ans);
	}
}

... Hmm, the subscript was difficult. .. Especially, it is difficult to set it to 0 at the very beginning of the cumulative sum.

Is there only a little practice? I'm glad that I knew the concept and the way of thinking itself. For the time being, I will end here. Well then ~.