Fragen Sie mit einem Aktualisierungsvorgang das K-te größte Zeichen in einem Bereich in einer Zeichenfolge ab

Ein Fenwick-Baum ist eine Datenstruktur, die Bereichsaktualisierungen und Bereichssuchen in O(log n)-Zeitkomplexität ermöglicht, auch bekannt als Binary Index Tree (BIT)

Das Grundkonzept besteht darin, für jeden Buchstaben in der Zeichenfolge ein Häufigkeitsarray zu führen und die Häufigkeit des i-ten Zeichens am Index i im Häufigkeitsarray aufzuzeichnen. Das Frequenzarray kann dann Bereichsaktualisierungen und Bereichsabfragen mithilfe von Fenwick Trees ermöglichen.

Problembehandlung

Sie können die folgende Abfrage verwenden, um das K-te größte Zeichen aus einer Zeichenfolge mit einem Aktualisierungsbereich von [L, R] -

zu extrahieren

• Erstellen Sie einen Segmentbaum – Erstellen Sie zunächst einen Segmentbaum, der die Häufigkeit jedes Zeichens in der Zeichenfolge speichert. Jeder Knoten des Segmentbaums speichert ein Häufigkeitsarray, das die Häufigkeit jedes Buchstabens im Bereich enthält, der den Indexbereich in der Zeichenfolge darstellt.

• Update – Sie können Zeichen in einer Zeichenfolge aktualisieren, indem Sie die übereinstimmenden Blattknoten im Segmentbaum aktualisieren, indem Sie die Häufigkeit einiger vorheriger Zeichen verringern und die Häufigkeit neuer Zeichen erhöhen.

  李>

• Suche nach dem K-ten größten Zeichen – Gehen Sie ausgehend von der Wurzel des Segmentbaums rekursiv zum relevanten Bereich des Index [L, R], um das K-te größte Zeichen in diesem Bereich zu finden. Mit einer modifizierten binären Suche kann an jedem Knoten das k-größte Zeichen im Bereich gefunden werden.

• Zeitkomplexität – ist O (log n), wobei n die Länge der Zeichenfolge ist. Die räumliche Komplexität des Segmentbaums beträgt O(n).

Grammatik

Unter der Annahme, dass die Zeichenfolge ursprünglich angegeben ist und aktualisiert werden kann, besteht die Abfrage darin, das k-größte Zeichen im Intervall [L, R] der Zeichenfolge zu finden. Die folgende Syntax kann verwendet werden -

1.Initialisierungszeichenfolge -

string str = "initial_string";

2. Aktualisieren Sie die Zeichenfolge am Index -

str[index] = new_character;

3. Finden Sie das k-größte Zeichen im Intervall [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

Algorithmus

Algorithmus zum Finden des K-ten größten Zeichens aus dem angegebenen Intervall [L, R] mit einigen Aktualisierungen -

• Schritt 1 – Initialisieren Sie ein Array A der Größe 26, wobei jedes Element A[i] die Anzahl des i-ten Zeichens (indiziert von 0) in der Zeichenfolge darstellt.

• Schritt 2 – Durchlaufen Sie die Zeichenfolge S von links nach rechts und aktualisieren Sie die Anzahl jedes Zeichens im Array A.

• Schritt 3 – Um Aktualisierungen zu verarbeiten, verwalten Sie ein separates Array B mit der gleichen Größe wie A, initialisiert auf Null.

• Schritt 4 – Wann immer ein Aktualisierungsvorgang durchgeführt wird, addieren Sie die Differenz zwischen der alten und neuen Zeichenanzahl zu den entsprechenden Elementen in B.

• Schritt 5 – Um das K-te größte Zeichen im Intervall [L, R] zu finden, berechnen Sie die kumulative Summe von A und B bis zum Index R und subtrahieren Sie die kumulative Summe von A und B bis zum Index L-1 . Dies gibt die Anzahl jedes Zeichens im Bereich [L, R] nach der Anwendung des Updates an.

• Schritt 6 – Sortieren Sie die Zeichen im Bereich [L, R] in absteigender Reihenfolge der Anzahl.

• Schritt 7 – Geben Sie das K-te Zeichen in sortierter Reihenfolge zurück.

Zu befolgende Methode

Methode 1

In diesem Beispiel wird die Zeichenfolge „abacaba“ als Anfangszeichenfolge verwendet. Die Konstruktorfunktion initialisiert den Segmentbaum, indem sie das Vorkommen jedes Zeichens in der Zeichenfolge zählt. Die Aktualisierungsfunktion aktualisiert Zeichenfolgen- und Segmentbäume, indem sie zunächst die Anzahl der alten Zeichen verringert und dann die Anzahl der neuen Zeichen erhöht. Die Abfragefunktion verwendet eine binäre Suche, um das k-größte Zeichen in [L,R] zurückzugeben.

Beispiel 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;
}

Ausgabe

abacaba
abacdba
5
5

Methode 2

Das Programm initialisiert zunächst ein zweidimensionales Array freq der Größe N x 26, wobei freq[i][j] die Häufigkeit des j-ten Zeichens bis zum i-ten Index im Präfix der Zeichenfolge s darstellt. Dann aktualisieren wir für jeden Index i das Freq-Array, indem wir die Zeichenanzahl am i-ten Index erhöhen und die Anzahl aller vorherigen Zeichen addieren.

Nachdem wir das Freq-Array initialisiert haben, führen wir zwei Abfragen aus. In jeder Abfrage berechnen wir die Zeichenanzahl im Bereich [L, R], indem wir die Zeichenanzahl vor Index L-1 von der Anzahl bei Index R subtrahieren. Anschließend iterieren wir über die Zeichenhäufigkeit von 0 bis 25 und verfolgen dabei die Anzahl der bisher gesehenen Zeichen. Wenn wir das k-te größte Zeichen erreichen, speichern wir seinen Index und verlassen die Schleife. Abschließend drucken wir das Zeichen aus, das dem gespeicherten Index entspricht.

Zwischen Abfragen aktualisieren wir die Zeichenfolge, indem wir das Zeichen an Index 4 in „a“ ändern. Um das Freq-Array effizient zu aktualisieren, aktualisieren wir die Anzahl der alten und neuen Zeichen am entsprechenden Index und berechnen dann die Anzahl aller nachfolgenden Zeichen mithilfe der aktualisierten Präfixsumme neu.

Beispiel 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;
}

Ausgabe

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

Fazit

Schließlich kann die Anforderung, das K-te größte Zeichen im Intervall [L, R] mit Aktualisierungen zu identifizieren, mithilfe einer Kombination aus Liniensegmentbäumen und binären Suchmethoden effizient gelöst werden. Die binäre Suchtechnik wird verwendet, um das K-te größte Zeichen im Bereich zu finden, und der Liniensegmentbaum wird verwendet, um die Häufigkeit des Auftretens von Zeichen in einem Bereich zu verfolgen.

Das obige ist der detaillierte Inhalt vonFragen Sie mit einem Aktualisierungsvorgang das K-te größte Zeichen in einem Bereich in einer Zeichenfolge ab. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!