Traduisez ce qui suit en utilisant C++ : requête de somme d'intervalles sans mises à jour

Dans cet article, nous recevrons un tableau de taille n, qui est un nombre entier. Nous calculerons ensuite la somme des éléments de l'index L à l'index R et effectuerons plusieurs requêtes, ou nous devrons calculer la somme de la plage donnée [L, R]. Par exemple -

Input : arr[] = {1, 2, 3, 4, 5}
   L = 1, R = 3
   L = 2, R = 4
Output : 9
   12

Input : arr[] = {1, 2, 3, 4, 5}
   L = 0, R = 4
   L = 1, R = 2
Output : 15
   5

Façons de trouver une solution

Il existe deux solutions à ce problème. La première consiste à utiliser des méthodes de force brute et des méthodes de somme de préfixes (efficaces).

Méthode Brute Force

Dans cette méthode, nous allons parcourir la plage donnée et imprimer la somme.

Exemple

#include<bits/stdc++.h>

using namespace std;

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int n = sizeof(arr)/sizeof(int); // size of given array.
   int L1 = 1, R1 = 3;
   int L2 = 2, R2 = 4;
   int sum = 0;
   for(int i = L1; i <= R1; i++) // traversing through the first range.
      sum += arr[i];
   cout << sum << "\n";
   sum = 0;
   for(int i = L2; i <= R2; i++) // traversing through the second range.
      sum += arr[i];
   cout << sum << "\n";
}

Sortie

9
12

Explication du code ci-dessus

Dans cette approche, nous parcourons simplement la plage donnée ; dans ce cas, ce programme est bon car sa complexité de temps de recherche est O (N), où N est le taille du tableau donné. Néanmoins, les choses changent lorsque nous recevons plusieurs requêtes Q, alors notre complexité devient O(N*Q), où Q est le nombre de requêtes et N est la taille du tableau donné. Malheureusement, cette complexité temporelle ne peut pas gérer des contraintes plus élevées, nous allons donc maintenant examiner une méthode efficace pour des contraintes plus élevées.

Méthode efficace

Dans cette méthode, nous allons créer un nouveau tableau appelé préfixe qui servira de préfixe et de tableau, puis nous répondrons à la somme de la plage donnée.

Exemple

#include<bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = {1, 2, 3, 4, 5};
   int n = sizeof(arr)/sizeof(int); // size of given array.
   int L1 = 1, R1 = 3;
   int L2 = 2, R2 = 4;
   int sum = 0;
   int prefix[n];
   for(int i = 0; i < n; i++){
      sum += arr[i];
      prefix[i] = sum;
   }

   if(L1) // to avoid segmentation fault
      cout << prefix[R1] - prefix[L1 - 1] << "\n";
   else
      cout << prefix[R1] << "\n";

   if(L2) // avoiding segmentation fault.
      cout << prefix[R2] - prefix[L2 - 1] << "\n";
   else
      cout << prefix[R2] << "\n";
}

Sortie

9
12

Explication du code ci-dessus

Dans cette méthode, nous stockons le préfixe et la valeur dans un tableau appelé préfixe. Maintenant, ce tableau rend notre programme très efficace car il nous donne une complexité temporelle de recherche de O(1), qui est la meilleure complexité que vous puissiez obtenir, donc lorsque nous recevons des requêtes Q, nous la complexité temporelle de recherche devient O(Q) , où Q est le nombre de requêtes.

Conclusion

Dans cet article, nous avons résolu un problème de recherche de plages et de requêtes sans mises à jour à l'aide de préfixes et de tableaux. Nous avons également appris un programme C++ pour ce problème et une solution complète (commune et efficace). Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que vous avez trouvé cet article utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!