Übersetzen Sie Folgendes mit C++: Intervallsummenabfrage ohne Aktualisierungen

In diesem Artikel erhalten wir ein Array der Größe n, bei dem es sich um eine ganze Zahl handelt. Wir berechnen dann die Summe der Elemente von Index L bis Index R und führen mehrere Abfragen durch, oder wir müssen die Summe des angegebenen Bereichs [L, R] berechnen. Zum Beispiel –

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

Möglichkeiten, eine Lösung zu finden

Es gibt zwei Lösungen für dieses Problem. Die erste Möglichkeit besteht in Brute-Force-Methoden und Präfixsummenmethoden (effizient).

Brute-Force-Methode

Bei dieser Methode iterieren wir über den angegebenen Bereich und drucken die Summe aus.

Beispiel

#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";
}

Ausgabe

9
12

Erklärung des obigen Codes

Bei diesem Ansatz iterieren wir einfach über den angegebenen Bereich; in diesem Fall ist dieses Programm gut, da seine Suchzeitkomplexität O (N) ist, wobei N die ist Größe des angegebenen Arrays. Nichtsdestotrotz ändern sich die Dinge, wenn uns mehrere Abfragen Q gegeben werden, dann wird unsere Komplexität zu O(N*Q), wobei Q die Anzahl der Abfragen und N die Größe des gegebenen Arrays ist. Leider kann diese Zeitkomplexität höhere Einschränkungen nicht bewältigen, daher werden wir uns nun mit einer effizienten Methode für höhere Einschränkungen befassen.

Effiziente Methode

In dieser Methode erstellen wir ein neues Array namens Präfix, das als Präfix und Array dient, und beantworten dann die Summe des angegebenen Bereichs.

Beispiel

#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";
}

Ausgabe

9
12

Erklärung des obigen Codes

In dieser Methode speichern wir das Präfix und den Wert in einem Array namens Präfix. Dieses Array macht unser Programm nun sehr effizient, da es uns eine Suchzeitkomplexität von O(1) gibt, was die beste Komplexität ist, die Sie bekommen können. Wenn wir also Q-Anfragen erhalten, werden wir Die Suchzeitkomplexität wird zu O(Q) , wobei Q die Anzahl der Abfragen ist.

Fazit

In diesem Artikel haben wir das Problem gelöst, Bereiche und Abfragen ohne Aktualisierungen mithilfe von Präfixen und Arrays zu finden. Wir haben auch ein C++-Programm für dieses Problem und eine vollständige Lösung (allgemein und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie fanden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonÜbersetzen Sie Folgendes mit C++: Intervallsummenabfrage ohne Aktualisierungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!