Terjemah yang berikut menggunakan C++: Pertanyaan jumlah selang tanpa kemas kini

Dalam artikel ini, kita akan diberikan tatasusunan saiz n, iaitu integer. Kami kemudiannya akan mengira jumlah elemen dari indeks L hingga indeks R dan melakukan berbilang pertanyaan, atau kami perlu mengira jumlah julat yang diberikan [L, R]. Contohnya -

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

Cara untuk mencari penyelesaian

Terdapat dua penyelesaian untuk masalah ini. Yang pertama adalah melalui kaedah brute force dan kaedah jumlah awalan (cekap).

Kaedah Brute Force

Dalam kaedah ini, kami akan mengulangi julat yang diberikan dan mencetak jumlahnya.

Contoh

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

Output

9
12

Penjelasan kod di atas

#🎜 hanya menilai kaedah ini, kami hanya menilai kaedah ini diberikan julat tertentu; dalam kes ini, program ini bagus kerana kerumitan masa cariannya ialah O(N), di mana N ialah saiz tatasusunan yang diberikan. Namun begitu, perkara berubah apabila kita diberi berbilang pertanyaan Q, maka kerumitan kita menjadi O(N*Q), di mana Q ialah bilangan pertanyaan dan N ialah saiz tatasusunan yang diberikan. Malangnya, kerumitan masa ini tidak dapat menangani kekangan yang lebih tinggi, jadi sekarang kita akan melihat kaedah yang cekap untuk kekangan yang lebih tinggi.

Kaedah cekap

Dalam kaedah ini kita akan mencipta tatasusunan baharu yang dipanggil awalan yang akan berfungsi sebagai awalan dan tatasusunan kami dan kemudian kami menjawab julat yang diberikan jumlahnya.

Contoh

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

Output

9
12

Penjelasan kod di atas

#🎜🎜 dalam kaedah ini dan kami akan menggunakan kaedah ini. nilai disimpan dalam tatasusunan yang dipanggil awalan. Kini, tatasusunan ini menjadikan program kami sangat cekap kerana ia memberikan kami kerumitan masa carian O(1), iaitu kerumitan terbaik yang anda boleh dapatkan, jadi apabila kami diberi pertanyaan Q, kami Kerumitan masa carian menjadi O(Q) , dengan Q ialah bilangan pertanyaan.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari julat dan pertanyaan tanpa kemas kini menggunakan awalan dan tatasusunan. Kami juga mempelajari program C++ untuk masalah ini dan penyelesaian lengkap (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Harap anda mendapati artikel ini membantu.

Atas ialah kandungan terperinci Terjemah yang berikut menggunakan C++: Pertanyaan jumlah selang tanpa kemas kini. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!