Interroger le Kième plus grand caractère d'une plage dans une chaîne, avec une opération de mise à jour

Un arbre Fenwick est une structure de données qui permet des mises à jour de plages et des recherches de plages dans une complexité temporelle O(log n), également connue sous le nom d'arbre d'index binaire (BIT)

Le concept de base est de conserver un tableau de fréquences pour chaque lettre de la chaîne, et la fréquence du i-ième caractère est enregistrée à l'index i dans le tableau de fréquences. Le réseau de fréquences peut ensuite permettre des mises à jour de plage et des requêtes de plage à l'aide d'arbres Fenwick.

Gestion des problèmes

Vous pouvez utiliser la requête suivante pour extraire le Kième plus grand caractère d'une chaîne, avec une plage de mise à jour de [L, R] -

• Créer un arbre de segments - Commencez par créer un arbre de segments, qui stocke la fréquence de chaque caractère dans la chaîne. Chaque nœud de l'arborescence de segments stocke un tableau de fréquences contenant la fréquence de chaque lettre de la plage, qui représente la plage d'index de la chaîne.

• Mise à jour - Vous pouvez mettre à jour les caractères d'une chaîne en mettant à jour les nœuds feuilles correspondants dans l'arborescence des segments en diminuant la fréquence de certains caractères précédents et en augmentant la fréquence des nouveaux caractères.

  李>

• Recherche du Kème plus grand caractère - En commençant par la racine de l'arborescence des segments, accédez de manière récursive à la plage pertinente de l'index [L, R] pour trouver le Kème plus grand caractère de cette plage. Le Kième plus grand caractère de la plage peut être trouvé à chaque nœud à l'aide d'une recherche binaire modifiée.

• Complexité temporelle - est O (log n), où n est la longueur de la chaîne. La complexité spatiale de l'arbre de segments est O(n).

Grammaire

En supposant que la chaîne est initialement donnée et peut être mise à jour, la requête consiste à trouver le k-ième plus grand caractère dans l'intervalle [L, R] de la chaîne. La syntaxe suivante peut être utilisée -

.

1.Chaîne d'initialisation -

string str = "initial_string";

2. Mettez à jour la chaîne à l'index -

str[index] = new_character;

3. Trouvez le k-ième plus grand caractère dans l'intervalle [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

Algorithme

Algorithme pour trouver le Kième plus grand caractère de l'intervalle donné [L, R] avec quelques mises à jour -

• Étape 1 - Initialisez un tableau A de taille 26, où chaque élément A[i] représente le nombre du i-ème caractère (indexé à partir de 0) dans la chaîne.

• Étape 2 - Parcourez la chaîne S de gauche à droite et mettez à jour le nombre de chaque caractère du tableau A.

• Étape 3 - Pour gérer les mises à jour, conservez un tableau B séparé de la même taille que A, initialisé à zéro.

• Étape 4 - Chaque fois qu'une opération de mise à jour est effectuée, ajoutez la différence entre l'ancien et le nouveau nombre de caractères aux éléments correspondants dans B.

• Étape 5 - Pour trouver le Kième plus grand caractère dans l'intervalle [L, R], calculez la somme cumulée de A et B jusqu'à l'indice R, et soustrayez la somme cumulée de A et B jusqu'à l'indice L-1 . Cela donne le nombre de chaque caractère dans la plage [L, R] après avoir appliqué la mise à jour.

• Étape 6 - Triez les caractères de la plage [L, R] par ordre décroissant de nombre.

• Étape 7 - Renvoyez le Kième caractère dans l'ordre trié.

Méthode à suivre

Méthode 1

Dans cet exemple, la chaîne "abacababa" est utilisée comme chaîne initiale. La fonction constructeur initialise l'arborescence de segments en comptant les occurrences de chaque caractère dans la chaîne. La fonction de mise à jour met à jour les arborescences de chaînes et de segments en décrémentant d'abord le nombre d'anciens caractères, puis en incrémentant le nombre de nouveaux caractères. La fonction de requête utilise une recherche binaire pour renvoyer le k-ième plus grand caractère dans [L,R].

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

Sortie

abacaba
abacdba
5
5

Méthode 2

Le programme initialise d'abord un tableau bidimensionnel freq de taille N x 26, où freq[i][j] représente la fréquence du j-ème caractère jusqu'au i-ème index dans le préfixe de la chaîne s. Ensuite, pour chaque index i, nous mettons à jour le tableau freq en incrémentant le nombre de caractères au i-ième index et en ajoutant le nombre de tous les caractères précédents.

Après avoir initialisé le tableau freq, nous exécutons deux requêtes. Dans chaque requête, nous calculons le nombre de caractères dans la plage [L, R] en soustrayant le nombre de caractères avant l'index L-1 du nombre à l'index R. Nous parcourons ensuite la fréquence des caractères de 0 à 25, en gardant une trace du nombre de caractères vus jusqu'à présent. Lorsque nous atteignons le Kième plus grand caractère, nous stockons son index et sortons de la boucle. Enfin, nous imprimons le caractère correspondant à l'index stocké.

Entre les requêtes, nous mettons à jour la chaîne en changeant le caractère à l'index 4 en "a". Pour mettre à jour efficacement le tableau freq, nous mettons à jour le nombre des anciens et des nouveaux caractères à l'index correspondant, puis recalculons le nombre de tous les caractères suivants en utilisant la somme des préfixes mise à jour.

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

Sortie

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

Conclusion

Enfin, la demande d'identification du Kième plus grand caractère dans l'intervalle [L, R] avec des mises à jour peut être résolue efficacement en utilisant une combinaison d'arbres de segments de ligne et de méthodes de recherche binaire. La technique de recherche binaire est utilisée pour localiser le Kème caractère le plus grand dans la plage, et l'arborescence de segments de ligne est utilisée pour suivre la fréquence d'apparition des caractères dans une plage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!