Tanya sempadan bawah K menggunakan awalan dan kemas kini tatasusunan tatasusunan pokok

Tatasusunan jumlah jujukan utama ialah koleksi yang mengumpul jumlah unsur bersilang sehingga indeks tertentu dicapai. Ini ialah strategi yang digunakan secara meluas dalam pemfaktoran semula kombinatorial untuk mengoptimumkan kerumitan masa. Tatasusunan pokok, juga dikenali sebagai Pokok Indeks Binari (BIT), ialah borang pangkalan data yang mengemas kini elemen dengan cekap dan mengira jumlah jujukan sebelumnya dalam kerumitan masa logaritma.

Dalam artikel ini, kita akan membincangkan cara menggunakan Fenwick Tree dalam C++ dengan peningkatan moden untuk mendedahkan had yang lebih kecil untuk nilai tertentu, dipanggil K, daripada siri tatasusunan terjumlah.

Tatabahasa

Sintaks mentakrifkan dua fungsi, kemas kini dan pertanyaan, dan fungsi utama untuk pepohon Fenwick, struktur data untuk pertanyaan julat yang cekap dan operasi kemas kini. Fungsi kemas kini menerima idx indeks, nilai val, saiz tatasusunan n, dan tatasusunan pokok Fenwick BIT. Ia mengemas kini pokok Fenwick dengan menambahkan val pada nod di index idx dan semua nenek moyangnya. Fungsi pertanyaan menerima indeks idx dan tatasusunan pokok Fenwick BIT. Ia mengembalikan jumlah terkumpul dari nod akar ke nod dengan idx indeks. Fungsi utama mengisytiharkan saiz n tatasusunan, awalan dan tatasusunan arr, dan tatasusunan pokok Fenwick BIT dimulakan kepada 0.

void update(int idx, int val, int n, int BIT[]) {
   while (idx <= n) {
      BIT[idx] += val;
      idx += (idx & -idx);
   }
}
int query(int idx, int BIT[]) {
   int sum = 0;
   while (idx > 0) {
      sum += BIT[idx];
      idx -= (idx & -idx);
   }
   return sum;
}
// Driver code
int main() {
   int n; 
   int arr[n+1];
   int BIT[n+1] = {0}; 
   return 0;
}

Algoritma

Untuk menentukan nilai minimum K dalam awalan dan tatasusunan dengan kemas kini pokok Fenwick, ikuti langkah kompleks di bawah -

• Segerakkan pokok Fenwick (BIT) bersaiz n+1, mulakan semua elemen kepada 0.

• Gunakan fungsi kemas kini() untuk mengubah suai Pokok Fenwick dengan awalan dan tatasusunan yang diberikan.

• Lakukan pertanyaan pada pokok Fenwick untuk menentukan sempadan bawah K. Lelaran bermula daripada bit paling ketara dalam perwakilan binari n kepada bit paling tidak bererti. Gunakan fungsi query() untuk mengesahkan sama ada jumlah awalan semasa adalah kurang daripada atau sama dengan K. Jika syarat ini dipenuhi, jumlah awalan semasa ditolak daripada K dan indeks dikemas kini untuk beralih ke bit seterusnya. Jika syarat tidak dipenuhi, beralih ke bit seterusnya tanpa mengemas kini indeks.

• Selepas melelaran melalui semua bit, indeks akan mewakili awalan dan sempadan bawah K dalam tatasusunan.

• Keluarkan indeks yang diperoleh sebagai sempadan bawah K.

Kaedah

• Kaedah 1 − Lakukan carian binari pada pokok Fenwick. Dalam kaedah ini, kami melakukan carian binari pada pokok Fenwick untuk mencari sempadan bawah K.

• Kaedah 2 - Carian binari dengan pembiakan tertunda pada pokok Fenwick.

Kaedah 1

Untuk menyelesaikan masalah ini, kami mula-mula menetapkan penunjuk kiri dan kanan masing-masing kepada 1 dan n (menunjukkan saiz awalan dan tatasusunan), dan kemudian menggunakan strategi carian binari untuk menentukan indeks i sepadan dengan jumlah awalan terbesar kurang daripada atau sama dengan K. Kemudian, bergantung pada sama ada nilai jumlah awalan [i] adalah kurang daripada atau sama dengan K, kedudukan penunjuk kiri atau penunjuk kanan dikemas kini.

Contoh

Mekanisme asas kod ini adalah untuk menggunakan struktur data yang dipanggil Fenwick Tree (juga dikenali sebagai Binary Indexed Tree). Tujuannya adalah untuk menentukan sempadan bawah nilai 'k' yang ditentukan dalam tatasusunan jumlah awalan. Ini dicapai dengan membina Pokok Fenwick menggunakan fungsi kemas kini yang menggabungkan awalan dan nilai setiap elemen dalam tatasusunan ke dalam kedudukan yang sepadan dalam Pokok Fenwick.

findLowerBound kemudian menggunakan algoritma carian binari untuk mengetahui sempadan bawah "k" dalam awalan dan tatasusunan dengan menanyakan fungsi. Fungsi ini mengira jumlah terkumpul nilai sehingga indeks semasa dalam pokok Fenwick. Akhirnya, kod itu akhirnya mengenal pasti awalan dan indeks sempadan bawah "k" dalam tatasusunan, dan memaparkan hasilnya kepada konsol.

#include <iostream>
using namespace std;
void update(int i, int v, int n, int b[]) {
    while (i <= n) {
        b[i] += v;
        i += (i & -i);
    }
}
int query(int i, int b[]) {
    int s = 0;
    while (i > 0) {
        s += b[i];
        i -= (i & -i);
    }
    return s;
}
int findLowerBound(int k, int n, int p[], int b[]) {
    int l = 1, r = n, idx = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        int msum = query(m, b);
        if (msum <= k) {
            idx = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return idx;
}
int main() {
    int n = 5;
    int p[] = {0, 1, 3, 6, 10, 15};
    int b[n + 1] = {0};
    for (int i = 1; i <= n; i++) {
        update(i, p[i], n, b);
    }
    int k = 10, idx;
    idx = findLowerBound(k, n, p, b);
    cout << "The lower bound of " << k << " is at index " << idx << " in the prefix sum array." << endl;
    return 0;
}

Output

The lower bound of 10 is at index 3 in the prefix sum array.

Kaedah 2

Untuk mengoptimumkan lagi pokok Fenwick, teknik yang dipanggil pembiakan malas boleh digunakan. Pendekatan ini memerlukan penangguhan kemas kini pada Pokok Fenwick sehingga ia benar-benar diperlukan, dengan itu mengurangkan bilangan kemas kini dan menjadikan proses pertanyaan lebih cekap.

Contoh

Kod ini menyediakan penyelesaian untuk mencari sempadan bawah nilai K yang diberikan dalam tatasusunan jumlah awalan. Tatasusunan jumlah awalan ialah tatasusunan di mana setiap elemen ialah jumlah elemen daripada indeks 0 hingga indeks itu dalam tatasusunan asal. Sempadan bawah ialah indeks pertama dalam tatasusunan jumlah awalan supaya jumlah elemen sehingga indeks itu sama atau melebihi K. Penyelesaian ini menggunakan struktur data pokok Fenwick dan teknik penyebaran lengah untuk meningkatkan kecekapan penyelesaian. Kod ini termasuk fungsi untuk mengubah suai pokok Fenwick, mengira jumlah awalan dan mencari sempadan bawah. Kod ini juga memulakan tatasusunan jumlah awalan, pokok Fenwick dan tatasusunan penyebaran tertunda. Akhirnya, ia mengeluarkan awalan dan sempadan bawah K dalam tatasusunan.

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

void update(int idx, int val, int n, int ft[], int lz[]) {
   while (idx  <= n) ft[idx] += val, idx += (idx & -idx);
}

int getPrefixSum(int idx, int ft[]) {
   int sum = 0;
   while (idx > 0) sum += ft[idx], idx -= (idx & -idx);
   return sum;
}

int findLowerBound(int K, int n, int ps[], int ft[], int lz[]) {
   int l = 1, r = n, lb = 0;
   while (l  <= r) {
      int m = (l + r) / 2, s = getPrefixSum(m, ft) + lz[m];
      if (s  <= K) lb = m, l = m + 1;
      else r = m - 1;
   }
   return lb;
}

int main() {
   int n = 5;
   int ps[] = {0, 1, 3, 6, 10, 15};
   int ft[n + 1], lz[n + 1]; memset(ft, 0, sizeof(ft)); memset(lz, 0, sizeof(lz));
   for (int i = 1; i  <= n; i++) update(i, ps[i] - ps[i - 1], n, ft, lz);
   int K = 10;
   int lb = findLowerBound(K, n, ps, ft, lz);
   cout << "For the given array with size " << n << " and prefix sum array [";
   for (int i = 1; i <= n; i++) {
      cout << ps[i];
      if (i < n) cout << ", ";
   }
   cout << "], the lower bound of " << K << " is at index " << lb << " in the prefix sum array." << endl;
   return 0;
}

Output

For the given array with size 5 and prefix sum array [1, 3, 6, 10, 15], the lower bound of 10 is at index 4 in the prefix sum array.

Kesimpulan

Perbincangan tentang perlombongan ambang nilai K yang sukar difahami daripada awalan dan tatasusunan yang direka dengan baik, dipertingkatkan dengan kemas kini yang memanfaatkan algoritma pepohon Fenwick yang bijak daripada dunia pengaturcaraan C++. Selami kerumitan dua kaedah cekap: carian binari pada pokok Fenwick dan carian binari pada pokok Fenwick dengan pembiakan malas. Berhati-hati memilih kaedah yang paling sesuai berdasarkan keperluan khusus dan kekangan masalah tertentu anda. Mudah-mudahan ini memberi penerangan tentang konsep dan pelaksanaan tugas sukar untuk mencari sempadan bawah pada K daripada pelbagai jumlah awalan dengan kemas kini, memanfaatkan kuasa pokok Fenwick yang tiada tandingan dalam alam C++.

Atas ialah kandungan terperinci Tanya sempadan bawah K menggunakan awalan dan kemas kini tatasusunan tatasusunan pokok. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!