Query the Kth largest character in a range in a string, with an update operation

Fenwick tree is a data structure that can perform range updates and range searches with O(log n) time complexity, also known as binary index tree (BIT)

The basic concept is to keep a frequency array for each letter in the string, and the frequency of the i-th character is recorded at index i in the frequency array. The frequency array can then allow range updates and range queries using Fenwick Trees.

Problem handling

You can use the following query to extract the Kth largest character from a string, with an update range of [L, R] -

• Building a Segment Tree - First create a segment tree, which stores the frequency of each character in the string. Each node of the segment tree stores a frequency array containing the frequency of each letter in the range, which represents the range of indexes in the string.

• Update - You can update characters in a string by updating the matching leaf nodes in the segment tree by decreasing the frequency of some previous characters and increasing the frequency of new characters.

  李>

• Kth largest character search - Starting from the root of the segment tree, recursively go to the relevant range [L, R] of the index to find the Kth largest character in that range . The Kth largest character in the range can be found at each node using a modified binary search.

• Time complexity - is O (log n), where n is the length of the string. The space complexity of the segment tree is O(n).

grammar

Assuming that the string is initially given and can be updated, the query is to find the k-th largest character in the interval [L, R] of the string. The following syntax can be used -

1.Initialization string -

string str = "initial_string";

2. Update the string at the index -

str[index] = new_character;

3. Find the k-th largest character in the interval [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

algorithm

Algorithm to find the Kth largest character from the given interval [L, R] and make some updates -

• Step 1 - Initialize an array A of size 26, where each element A[i] represents the count of the i-th character (indexed from 0) in the string.

• Step 2 - Traverse the string S from left to right and update the count of each character in the array A.

• Step 3 - To handle updates, maintain a separate array B of the same size as A, initialized to zero.

• Step 4 - Whenever an update operation is performed, add the difference between the old and new character counts to the corresponding element in B.

• Step 5 - To find the Kth largest character in the interval [L, R], calculate the cumulative sum of A and B up to index R, and subtract the cumulative sum of A and B and up to index L-1. This gives the count of each character in the range [L, R] after applying the update.

• Step 6 - Sort the characters in the range [L, R] in descending order of count.

• Step 7 - Return the Kth character in sorted order.

Method to follow

method 1

In this example, the string "abacaba" is used as the initial string. The constructor function initializes the segment tree by counting the occurrences of each character in the string. The update function updates string and segment trees by first decrementing the count of old characters and then incrementing the count of new characters. The query function uses a binary search to return the k-th largest character in [L,R].

Example 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

Method 2

The program first initializes a two-dimensional array freq of size N x 26, where freq[i][j] represents the frequency of the j-th character up to the i-th index in the prefix of string s. Then, for each index i, we update the freq array by incrementing the character count at the i-th index and adding the counts of all previous characters.

After initializing the freq array, we execute two queries. In each query, we calculate the character count in the range [L, R] by subtracting the character count before index L-1 from the count at index R. We then iterate over the character frequency from 0 to 25, keeping track of the number of characters seen so far. When we reach the Kth largest character, we store its index and break out of the loop. Finally, we print the character corresponding to the stored index.

Between two queries, we update the string by changing the character at index 4 to "a". To efficiently update the freq array, we update the count of the old and new characters at the corresponding index, and then recalculate the count of all subsequent characters using the updated prefix sum.

Example 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

in conclusion

Finally, the request to identify the Kth largest character in the interval [L, R] with updates can be effectively solved using a combination of line segment trees and binary search methods. The binary search technique is used to locate the Kth largest character in the range, and the line segment tree is used to track the frequency of occurrence of characters in a range.

The above is the detailed content of Query the Kth largest character in a range in a string, with an update operation. For more information, please follow other related articles on the PHP Chinese website!