Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Beaucoup de questions, un seul prétraitement

Beaucoup de questions, un seul prétraitement

Exercice de la série « Tableaux et parcours »intermediaire

Le problème. Un tableau de ventes journalières, et des centaines de questions de la forme « quel est le total du jour i au jour j, bornes incluses ? ». Resommer à chaque question coûte trop cher.

Écrivez totaux(ventes, questions) où questions est un tableau de paires [i, j]. Renvoyez un tableau avec un total par question, dans le même ordre.

Appel Résultat attendu
totaux([1, 2, 3, 4], [[0, 1], [1, 3], [2, 2]]) [3, 9, 3]
totaux([5], [[0, 0]]) [5]
totaux([], []) []
totaux([1, 2], [[0, 1], [0, 0], [1, 1]]) [3, 1, 2]

Ce qu'on attend. Un prétraitement en O(n), puis O(1) par question.

Le piège. Les bornes sont incluses, et un tableau de sommes préfixes est décalé d'une case par rapport au tableau d'origine. Le décalage est là, et nulle part ailleurs.

Cas de test

Écrire le code et le faire exécuter →

Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.

La leçon qui prépare cet exercice

Les autres exercices de « Tableaux et parcours »