Queries to find Kth greatest character in a range [ L , R ] from a string with updates | C ++ Program to implement the above approach ; Maximum Size of a String ; Fenwick Tree to store the frequencies of 26 alphabets ; Size of the String . ; Function to update Fenwick Tree for Character c at index val ; Add val to current node Fenwick Tree ; Move index to parent node in update View ; Function to get sum of frequencies of character c till index ; Stores the sum ; Add current element of Fenwick tree to sum ; Move index to parent node in getSum View ; Function to create the Fenwick tree ; Function to print the kth largest character in the range of l to r ; Stores the count of characters ; Stores the required character ; Calculate frequency of C in the given range ; Increase count ; If count exceeds K ; Required character found ; Function to update character at pos by character s ; 0 based index system ; Driver Code ; Makes the string 1 - based indexed ; Number of queries ; Construct the Fenwick Tree
#include " bits / stdc + + . h " NEW_LINE using namespace std ; const int maxn = 100005 ; int BITree [ 26 ] [ maxn ] ; int N ; void update_BITree ( int index , char C , int val ) { while ( index <= N ) { BITree [ C - ' a ' ] [ index ] += val ; index += ( index & - index ) ; } } int sum_BITree ( int index , char C ) { int s = 0 ; while ( index ) { s += BITree [ C - ' a ' ] [ index ] ; index -= ( index & - index ) ; } return s ; } void buildTree ( string str ) { for ( int i = 1 ; i <= N ; i ++ ) { update_BITree ( i , str [ i ] , 1 ) ; } cout << endl ; } char printCharacter ( string str , int l , int r , int k ) { int count = 0 ; char ans ; for ( char C = ' z ' ; C >= ' a ' ; C -- ) { int times = sum_BITree ( r , C ) - sum_BITree ( l - 1 , C ) ; count += times ; if ( count >= k ) { ans = C ; break ; } } return ans ; } void updateTree ( string str , int pos , char s ) { int index = pos ; update_BITree ( index , str [ index ] , -1 ) ; str [ index ] = s ; update_BITree ( index , s , 1 ) ; } int main ( ) { string str = " abcddef " ; N = str . size ( ) ; str = ' # ' + str ; int Q = 3 ; buildTree ( str ) ; cout << printCharacter ( str , 1 , 2 , 2 ) << endl ; updateTree ( str , 4 , ' g ' ) ; cout << printCharacter ( str , 1 , 5 , 4 ) << endl ; return 0 ; }