Introduction aux algorithmes avec somme cumulée Java

Résumé de l'article

Il s'agit d'une série d'articles que j'ai compilés dans mon étude et mon mémo. Le cinquième. Cliquez ici pour les articles précédents.

Dans cet article

• ** Somme cumulée **

Je vais étudier sur. Terminons la section d'exploration et étudions un autre algorithme (ce qui vous intéressait dans le concours hebdomadaire).

Somme cumulée

Cela semble être une technique de calcul. Il semble pratique de trouver la somme des sections avec le tableau.

Référence: Etre capable d'écrire la somme cumulée sans réfléchir!

Je vais vous l'expliquer pour le moment.

Séquence a, {1,3,1,4,7,6,1,0,9} Dirons-nous cela? Par exemple, supposons que l'on vous demande de trouver la somme du 3e au 5e de cette séquence.

Méthode normale

a: Ajoutez simplement le 3ème au 5ème de {1,3, ** 1,4,7 **, 6,1,0,9}. La réponse est 1 + 4 + 7 = 12

Utiliser la somme cumulée

En plus de a, créez un tableau b qui stocke la somme jusqu'au i-ième de a. b：{0,1,4,5,9,16,22,23,23,32} Si vous écrivez a_1 comme le premier élément de a, b_1 = 0 (corrigé ici. Les indices seront décalés de un par la suite) 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 ...

Je me sens dit. À ce moment, la somme du 3e au 5e de a est calculée comme suit. b_6 - b_3 = 16 - 4 = 12

Les détails sont les suivants.

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

Comprenez-vous en quelque sorte? En sauvegardant la somme dans l'ordre du front, vous n'avez pas à vous soucier d'ajouter 3ème + 4ème + 5ème!

De quoi êtes-vous heureux?

Par exemple, lorsque vous devez trouver la somme de ● à ▲ plusieurs fois (en supposant un problème avec de nombreuses variations de ● et ▲), vous devez retourner la boucle encore et encore de la manière habituelle. Il y en a, mais si vous utilisez la somme cumulée, vous pouvez trouver la somme totale (avec O (1)) en un seul coup.

Regardons le problème.

exemple

Exemple: AtCoder --abc037-c "total"

N K
a1 .. aN

C'est le problème. C'est juste une question de somme cumulative. Vous devez ajouter K pièces N-K + 1 fois. Le montant du calcul est O (K * (N-K + 1)). De plus, si vous faites un mauvais choix (K = N / 2, etc.), vous constaterez que cela coûte O (N ^ 2). Ce n'est pas à temps. C'est pourquoi la somme cumulée entre en jeu. "K additions sont N-K + 1 fois", mais si vous utilisez la somme cumulée, "K additions" peut être fait avec O (1), donc la quantité de calcul est à peu près O (N). ..

La politique est la suivante.

--Préparer un tableau pour contenir la somme cumulée

• La somme de chacun de 1 ~ K, 2 ~ K + 1,3 ~ K + 2, ..., N-K + 1 ~ N est calculée par la séquence de sommes cumulées, et enfin la somme est la réponse.

Ensuite, voici un exemple de réponse.

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 pour recevoir des entrées
		long b[] = new long[n + 1]; //Stocker la somme cumulée

		for (int i = 0; i < n; i++) {
			//Recevoir une entrée
			a[i] = sc.nextLong();
		}

		for (int i = 1; i <= n; i++) {
			//Calcul de la somme cumulée
			b[i] = b[i - 1] + a[i - 1];
		}

		long ans = 0; //Stockage des réponses
		for (int i = 0; i < n - k + 1; i++) {
			ans += b[i + k] - b[i];
		}

		System.out.println(ans);
	}
}

... Hmm, c'était difficile à l'indice. .. Surtout, il est difficile de le mettre à 0 au tout début de la somme cumulée.

N'y a-t-il qu'un peu de pratique? Je suis content de connaître le concept et la manière de se penser. Pour le moment, je vais terminer ici. Eh bien ~.