Queries to find Kth greatest character in a range [ L , R ] from a string with updates | Java 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
import java . util . * ; class GFG { static int maxn = 100005 ; static int [ ] [ ] BITree = new int [ 26 ] [ maxn ] ; static int N ; static void update_BITree ( int index , char C , int val ) { while ( index <= N ) { BITree [ C - ' a ' ] [ index ] += val ; index += ( index & - index ) ; } } static int sum_BITree ( int index , char C ) { int s = 0 ; while ( index > 0 ) { s += BITree [ C - ' a ' ] [ index ] ; index -= ( index & - index ) ; } return s ; } static void buildTree ( String str ) { for ( int i = 1 ; i <= N ; i ++ ) { update_BITree ( i , str . charAt ( i ) , 1 ) ; } System . out . println ( ) ; } static char printCharacter ( String str , int l , int r , int k ) { int count = 0 ; char ans = 0 ; 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 ; } static void updateTree ( String str , int pos , char s ) { int index = pos ; update_BITree ( index , str . charAt ( index ) , - 1 ) ; str = str . substring ( 0 , index ) + s + str . substring ( index + 1 ) ; update_BITree ( index , s , 1 ) ; } public static void main ( String [ ] args ) { String str = " abcddef " ; N = str . length ( ) ; str = ' / ' + str ; int Q = 3 ; buildTree ( str ) ; System . out . print ( printCharacter ( str , 1 , 2 , 2 ) + "NEW_LINE"); updateTree ( str , 4 , ' g ' ) ; System . out . print ( printCharacter ( str , 1 , 5 , 4 ) + "NEW_LINE"); } }