[Java] Introduction to algorithms in java-cumulative sum

4 minute read

Article summary

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

# article
4 Introduction to algorithms with java-Search (bit full search)
3 Introduction to algorithms with java-Search (breadth-first search)
2 Introduction to algorithms with java-Search (depth-first search)
1 Introduction to algorithms with java-Search (full search, binary search)

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”

Click here to display problem sentences and input examples
* Please refer to the problem link as much as possible </summary> <div>


(Section start) 【Problem statement】 Given a sequence of length N {ai} and an integer K greater than or equal to 1 and less than or equal to N. This sequence has N−K + 1 contiguous subsequences of length K. Find the sum of the values contained in each of these subsequences.

[Restrictions] All inputs are integers 1≤K≤N≤10^5 0≤ai≤10^8

【input】 Input is given from standard input in the following format.

N K
a1 .. aN

【output】 Output the sum of the total N−K + 1 values contained in the subsequence.

(End of section)


</div></details>

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 ~.