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.

# 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

(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)


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

Recommended Posts

Introduction to algorithms in java-cumulative sum
Introduction to algorithms in java-lexicographic order / combination omnivorous (part1)
Introduction to algorithms with java-Shakutori method
Introduction to algorithms with java --Search (depth-first search)
Introduction to algorithms with java --Search (breadth-first search)
Introduction to Ruby 2
Introduction to web3j
Introduction to Micronaut 1 ~ Introduction ~
[Java] Introduction to Java
Introduction to migration
Introduction to java
Introduction to Doma
Introduction to Ratpack (Extra Edition) --Ratpack written in Kotlin
Introduction to algorithms with java --Search (bit full search)
Introduction to algorithms with java-Search (Full search, Binary search)
Introduction to JAR files
Sum from Java_1 to 100
Introduction to Ratpack (8)-Session
Introduction to bit operation
Introduction to Ratpack (6) --Promise
Introduction to Ratpack (9) --Thymeleaf
Understand the characteristics of Scala in 5 minutes (Introduction to Scala)
Introduction to PlayFramework 2.7 ① Overview
Introduction to Android Layout
To debug in eclipse
Introduction to design patterns (introduction)
Introduction to Practical Programming
Introduction to javadoc command
Introduction to jar command
Introduction to Ratpack (2)-Architecture
Introduction to lambda expression
Introduction to java command
Introduction to Keycloak development
Introduction to javac command
[Introduction to MVEL] Aiming to be the best MVELer in the world
Introduction to Rakefile that can be done in about 10 minutes
An introduction to functional programming for object-oriented programmers in Elm
Introduction to Parallel Processing + New Parallel Execution Unit in Ruby Ractor
Introduction to Design Patterns (Builder)
Introduction to Android application development
Introduction to Ratpack (5) --Json & Registry
Introduction to Metabase ~ Environment Construction ~
Introduction to Ratpack (7) --Guice & Spring
Refer to enum in Thymeleaf
(Dot installation) Introduction to Java8_Impression
Introduction to Design Patterns (Composite)
Introduction to Micronaut 2 ~ Unit test ~
Introduction to JUnit (study memo)
Introduction to Spring Boot ① ~ DI ~
Introduction to design patterns (Flyweight)
[Java] Introduction to lambda expressions
Introduction to Spring Boot ② ~ AOP ~
Introduction to Apache Beam (2) ~ ParDo ~
Introduction to EHRbase 2-REST API
Introduction to design patterns Prototype
[Java] Introduction to Stream API
Introduction to Design Patterns (Iterator)
Introduction to Spring Boot Part 1
Introduction to Ratpack (1) --What is Ratpack?
Introduction to Design Patterns (Strategy)
[Introduction to rock-paper-scissors games] Java