Tanya aksara terbesar Kth dalam julat dalam rentetan, dengan operasi kemas kini

Pepohon Fenwick ialah struktur data yang membolehkan kemas kini julat dan carian julat dalam kerumitan masa O(log n), juga dikenali sebagai Pokok Indeks Binari (BIT)

Konsep asas adalah untuk menyimpan tatasusunan frekuensi untuk setiap huruf dalam rentetan, dan kekerapan aksara ke-i direkodkan pada indeks i dalam tatasusunan frekuensi. Tatasusunan frekuensi kemudiannya boleh membenarkan kemas kini julat dan pertanyaan julat menggunakan Pokok Fenwick.

Pengendalian masalah

Anda boleh menggunakan pertanyaan berikut untuk mengekstrak aksara terbesar Kth daripada rentetan, dengan julat kemas kini [L, R] -

• Bina Pokok Segmen - Mulakan dengan mencipta pokok segmen, yang menyimpan kekerapan setiap aksara dalam rentetan. Setiap nod pokok segmen menyimpan tatasusunan frekuensi yang mengandungi kekerapan setiap huruf dalam julat, yang mewakili julat indeks dalam rentetan.

• Kemas kini - Anda boleh mengemas kini aksara dalam rentetan dengan mengemas kini nod daun yang sepadan dalam pokok segmen dengan mengurangkan kekerapan beberapa aksara sebelumnya dan meningkatkan kekerapan aksara baharu.

  李>

• Carian aksara terbesar ke-1 - Bermula pada akar pokok segmen, pergi secara rekursif ke julat indeks [L, R] yang berkaitan untuk mencari aksara terbesar K dalam julat itu. Aksara terbesar Kth dalam julat boleh didapati pada setiap nod menggunakan carian binari yang diubah suai.

• Kerumitan masa - ialah O (log n), dengan n ialah panjang rentetan. Kerumitan ruang bagi pokok segmen ialah O(n).

Tatabahasa

Dengan mengandaikan bahawa rentetan pada mulanya diberikan dan boleh dikemas kini, pertanyaannya adalah untuk mencari aksara terbesar ke-k dalam selang [L, R] rentetan Sintaks berikut boleh digunakan -

1. Rentetan permulaan -

string str = "initial_string";

2. Kemas kini rentetan pada indeks -

str[index] = new_character;

3 Cari aksara terbesar ke-k dalam selang [P, T] -

// initialize frequency array of size 26 
int freq[26] = {0};

// count the frequency of each character in the range
for (int i = P; i <= T; i++) {
   freq[str[i] - 'a']++;
}

// find k th greatest character
int cont = 0;
for (int i = 25; i >= 0; i--) {
   cont += freq[i];
   if (cont >= k) {
      return (char) (i + 'a');
   }
}

// if k th is larger than total no. of different characters in interval,

// give special character or throw exception

Algoritma

Algoritma untuk mencari aksara terbesar K dari selang yang diberikan [L, R] dengan beberapa kemas kini -

• Langkah 1 - Mulakan tatasusunan A bersaiz 26, di mana setiap elemen A[i] mewakili kiraan aksara ke-i (diindeks daripada 0) dalam rentetan.

• Langkah 2 - Lintas rentetan S dari kiri ke kanan dan kemas kini kiraan setiap aksara dalam tatasusunan A.

• Langkah 3 - Untuk mengendalikan kemas kini, kekalkan tatasusunan B yang berasingan dengan saiz yang sama seperti A, dimulakan kepada sifar.

• Langkah 4 - Setiap kali operasi kemas kini dilakukan, tambahkan perbezaan antara kiraan aksara lama dan baharu pada elemen yang sepadan dalam B.

• Langkah 5 - Untuk mencari aksara terbesar K dalam selang [L, R], hitung jumlah terkumpul A dan B sehingga indeks R, dan tolak jumlah terkumpul A dan B sehingga indeks L-1 . Ini memberikan kiraan setiap aksara dalam julat [L, R] selepas menggunakan kemas kini.

• Langkah 6 - Isih aksara dalam julat [L, R] dalam tertib kiraan menurun.

• Langkah 7 - Kembalikan aksara Kth dalam susunan yang disusun.

Kaedah untuk diikuti

Kaedah 1

Dalam contoh ini, rentetan "abacaba" digunakan sebagai rentetan awal. Fungsi pembina memulakan pepohon segmen dengan mengira kejadian setiap aksara dalam rentetan. Fungsi kemas kini mengemas kini rentetan dan pepohon segmen dengan mula-mula mengurangkan kiraan aksara lama dan kemudian menambah kiraan aksara baharu. Fungsi pertanyaan menggunakan carian binari untuk mengembalikan aksara terbesar ke-k dalam [L,R].

Contoh 1

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

const int N = 1e5+5;

struct NODE {
   int E, F, cnt[26];
} tree[4*N];

string W;

void build(int X, int E, int F) {
   tree[X].E = E, tree[X].F = F;
   if(E == F) {
      tree[X].cnt[W[E]-'a']++;
      return;
   }
   int mid = (E+F)/2;
   build(2*X, E, mid);
   build(2*X+1, mid+1, F);
   for(int i=0; i<26; i++) {
      tree[X].cnt[i] = tree[2*X].cnt[i] + tree[2*X+1].cnt[i];
   }
}

void update(int X, int E, int F, int idx, char ch) {
   if(E == F) {
      tree[X].cnt[W[E]-'a']--;
      W[E] = ch;
      tree[X].cnt[W[E]-'a']++;
      return;
   }
   int mid = (E+F)/2;
   if(idx <= mid) {
      update(2*X, E, mid, idx, ch);
   } else {
      update(2*X+1, mid+1, F, idx, ch);
   }
   for(int i=0; i<26; i++) {
      tree[X].cnt[i] = tree[2*X].cnt[i] + tree[2*X+1].cnt[i];
   }
}

int QUERY(int X, int E, int F, int k) {
   if(E == F) {
      return E;
   }
   int mid = (E+F)/2;
   int cnt = 0;
   for(int i=0; i<26; i++) {
      cnt += tree[2*X].cnt[i];
   }
   if(k <= cnt) {
      return QUERY(2*X, E, mid, k);
   } else {
      return QUERY(2*X+1, mid+1, F, k-cnt);
   }
}

int main() {
   W = "abacaba";
   int n = W.length();
   build(1, 0, n-1);

   cout << W << endl;

   update(1, 0, n-1, 4, 'd');

   cout << W << endl;

   int P = 5;
   int Q = 2;
   int R = 6;
   cout << QUERY(1, 0, n-1, R) << endl;
   cout << QUERY(1, 0, n-1, Q+P-1) << endl;
   return 0;
}

Output

abacaba
abacdba
5
5

Kaedah 2

Atur cara mula-mula memulakan frekuensi tatasusunan dua dimensi bersaiz N x 26, di mana freq[i][j] mewakili kekerapan aksara ke-j sehingga indeks ke-i dalam awalan rentetan s. Kemudian, untuk setiap indeks i, kami mengemas kini tatasusunan freq dengan menambah kiraan aksara pada indeks ke-i dan menambah kiraan semua aksara sebelumnya.

Selepas memulakan tatasusunan freq, kami melaksanakan dua pertanyaan. Dalam setiap pertanyaan, kami mengira kiraan aksara dalam julat [L, R] dengan menolak kiraan aksara sebelum indeks L-1 daripada kiraan pada indeks R. Kami kemudian mengulangi kekerapan aksara dari 0 hingga 25, menjejaki bilangan aksara yang dilihat setakat ini. Apabila kami mencapai aksara terbesar Kth, kami menyimpan indeksnya dan keluar dari gelung. Akhir sekali, kami mencetak aksara yang sepadan dengan indeks yang disimpan.

Di antara pertanyaan, kami mengemas kini rentetan dengan menukar aksara pada indeks 4 kepada "a". Untuk mengemas kini tatasusunan kekerapan dengan cekap, kami mengemas kini kiraan aksara lama dan baharu pada indeks yang sepadan, dan kemudian mengira semula kiraan semua aksara berikutnya menggunakan jumlah awalan yang dikemas kini.

Contoh 1

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

const int N = 1e5+5;
int Freq[N][26];

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);

   string Y = "programming code";
   int U = Y.size();

   for (int i = 0; i < U; i++) {
      Freq[i+1][Y[i]-'a']++;
      for (int j = 0; j < 26; j++) {
         Freq[i+1][j] += Freq[i][j];
      }
   }

   int Q = 2;
   while (Q--) {
      int l = 2, r = 9, k = 3;
      int cont = 0, ans;
      for (int i = 0; i < 26; i++) {
         cont += Freq[r][i] - Freq[l-1][i];
         if (cont >= k) {
            ans = i;
            break;
         }
      }
      cout << "The " << k << "rd greatest character in range [" << l << "," << r << "] is " << char(ans+'a') << "\n";

      Y[4] = 'a'; // update
      for (int i = 4; i < U; i++) {
         Freq[i+1][Y[i]-'a']++;
         Freq[i+1][Y[i-4]-'a']--;
         for (int j = 0; j < 26; j++) {
            Freq[i+1][j] += Freq[i][j];
         }
      }
   }

   return 0;
}

Output

The 3rd greatest character in range [2,9] is i
The 3rd greatest character in range [2,9] is a

Kesimpulan

Akhir sekali, permintaan untuk mengenal pasti aksara terbesar K dalam selang [L, R] dengan kemas kini boleh diselesaikan dengan cekap menggunakan gabungan pokok segmen garisan dan kaedah carian binari. Teknik carian binari digunakan untuk mencari aksara terbesar K dalam julat, dan pokok segmen garisan digunakan untuk menjejak kekerapan kemunculan aksara dalam julat.

Atas ialah kandungan terperinci Tanya aksara terbesar Kth dalam julat dalam rentetan, dengan operasi kemas kini. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!