Menggunakan tatasusunan pepohon (pertanyaan luar talian), hitung bilangan elemen yang lebih besar daripada K dalam julat L hingga R

Dalam bidang sains komputer, kita perlu berurusan dengan set data yang besar yang termasuk operasi pilih pertanyaan dan kemas kini. Melaksanakan operasi ini dalam masa nyata dengan kerumitan masa yang rendah adalah tugas yang mencabar untuk pembangun.

Menggunakan pokok Fenwick ialah cara yang berkesan untuk menyelesaikan masalah pertanyaan berasaskan julat ini.

Fenwick Tree ialah struktur data yang boleh mengemas kini elemen dengan cekap dan mengira jumlah awalan nombor dalam jadual. Ia juga dipanggil pokok indeks binari.

Dalam artikel ini, kita akan membincangkan cara mencari bilangan unsur yang lebih besar daripada K dalam julat L hingga R menggunakan pokok Fenwick.

Senario input dan output

Andaikan anda mempunyai tatasusunan dengan elemen N dan anda ingin mencari bilangan elemen dalam tatasusunan yang lebih besar daripada K dalam julat L hingga R.

Input: 
arr = {1, 15, 12, 13, 6, 18, 14, 10, 23, 41, 16, 9}
N = 11, K = 17, L = 1, R = 8
Output: 
2

Apakah pertanyaan luar talian?

Pertanyaan luar talian ialah operasi pertanyaan yang dilakukan pada set data yang telah ditetapkan. Dalam erti kata lain, operasi ini dilakukan hanya pada set data yang tidak diubah suai lagi semasa memproses pertanyaan.

Menggunakan Pokok Fenwick

Di sini, kami akan menggunakan pokok Fenwick, yang mempunyai vektor untuk setiap nod, yang mengandungi semua elemen tatasusunan mengikut tertib. Kami kemudian menggunakan carian binari untuk menjawab setiap pertanyaan dan mengira bilangan elemen.

• Buat dua fungsi, updateTree() dan total(), untuk mengemas kini dan mendapatkan semula jumlah awalan dalam BIT masing-masing.

• Seterusnya, cipta satu lagi fungsi yang akan mengira elemen dalam julat L hingga R yang lebih besar daripada "K". Fungsi ini menerima nilai input "arr", "N", "L", "R" dan "K".

• Pengiraan dikira dengan menolak jumlah kumulatif K daripada jumlah kumulatif julat maksimum N.

Untuk mengecualikan unsur luar julat, tolak jumlah terkumpul L-1 (jika L lebih besar daripada 1).

Contoh

#include <iostream>
#include <vector>
using namespace std;

// Updating the Fenwick Tree
void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

// Counting the number of elements
int elementsGreaterThanK(vector<int>& arr, int N, int K, int L, int R) {
   vector<int> BIT(N+1, 0);

   for (int i = L; i <= R; i++) {
      updateTree(BIT, arr[i], 1);
   }

   int count = total(BIT, N) - total(BIT, K);
   if (L > 1) {
      count -= total(BIT, L-1);
   }
   return count;
}

int main() {
   vector<int> arr = {0, 5, 2, 3, 6, 8, 7, 1, 8, 4, 6, 9};
   int N = 11; // Total range of values
   int K = 4; // Highest value
   int L = 1; // Start index of the range
   int R = 8; // End index of the range

   int count = elementsGreaterThanK(arr, N, K, L, R);
   cout << "Number of elements greater than " << K << " in the range [" << L << ", " << R << "]: " << count << endl;

   return 0;
}

Output

Number of elements greater than 4 in the range [1, 8]: 5

Kaedah Alternatif

Di sini kami akan mencipta vektor berasingan untuk menyimpan pertanyaan. Setiap pertanyaan terdiri daripada dua pembolehubah, index dan val. indeks digunakan untuk menyimpan kedudukan dalam tatasusunan, manakala val digunakan untuk menyimpan nilai elemen pada indeks tersebut. Pendekatan ini membolehkan pembangun melakukan pelbagai operasi pertanyaan. Selain itu, kami menggunakan BIT untuk mengira bilangan elemen yang lebih besar daripada K untuk setiap pertanyaan.

Contoh

#include <iostream>
#include <vector>
using namespace std;
struct Query {
   int index;
   int val;
};

void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

vector<int> elementsGreaterThanK(vector<int>& arr, vector<Query>& queries, int K) {
   int N = arr.size();
   vector<int> BIT(N+1, 0);
   vector<int> result;

   for (int i = 0; i < N; i++) {
      updateTree(BIT, i+1, (arr[i] > K) ? 1 : 0);
   }

   for (auto query : queries) {
      if (query.val > K) {
         result.push_back(total(BIT, query.index));
      }
      else {
         result.push_back(0);
      }
   }

   return result;
}

int main() {
   vector<int> arr = {3, 14, 32, 7, 11, 5, 8, 6, 16, 2, 15};
   vector<Query> queries = {{2, 4}, {5, 3}, {3, 6}, {0, 3}};
   int K = 2;

   vector<int> counts = elementsGreaterThanK(arr, queries, K);

   for (int count : counts) {
      cout << "Number of elements greater than " << K << ": " << count << endl;
   }

   return 0;
}

Output

Number of elements greater than 2: 2
Number of elements greater than 2: 5
Number of elements greater than 2: 3
Number of elements greater than 2: 0

Kesimpulan

Kita hanya boleh mengulang tatasusunan daripada indeks L kepada R dan menambah 1 setiap kali elemen tatasusunan lebih besar daripada K untuk mencari jawapan bagi setiap pertanyaan. Walau bagaimanapun, untuk mengurangkan kerumitan masa, kami menggunakan Fenwick tree untuk melaksanakan operasi pertanyaan sedemikian. Kami juga boleh menggunakan Pokok Segmen Garisan dan Jadual Jarang dan bukannya pokok Fenwick untuk melaksanakan operasi pertanyaan sedemikian.

Atas ialah kandungan terperinci Menggunakan tatasusunan pepohon (pertanyaan luar talian), hitung bilangan elemen yang lebih besar daripada K dalam julat L hingga R. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!