Queries to find Kth greatest character in a range [ L , R ] from a string with updates | 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
let maxn = 100005 ; let BITree = new Array ( 26 ) ; for ( let i = 0 ; i < 26 ; i ++ ) { BITree [ i ] = new Array ( maxn ) ; for ( let j = 0 ; j < maxn ; j ++ ) { BITree [ i ] [ j ] = 0 ; } } let N ; function update_BITree ( index , C , val ) { while ( index <= N ) { BITree [ C . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] [ index ] += val ; index += ( index & - index ) ; } } function sum_BITree ( index , C ) { let s = 0 ; while ( index > 0 ) { s += BITree [ C . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] [ index ] ; index -= ( index & - index ) ; } return s ; } function buildTree ( str ) { for ( let i = 1 ; i <= N ; i ++ ) { update_BITree ( i , str [ i ] , 1 ) ; } document . write ( " " ) ; } function printCharacter ( str , l , r , k ) { let count = 0 ; let ans = 0 ; for ( let C = ' ' . charCodeAt ( 0 ) ; C >= ' ' . charCodeAt ( 0 ) ; C -- ) { let times = sum_BITree ( r , String . fromCharCode ( C ) ) - sum_BITree ( l - 1 , String . fromCharCode ( C ) ) ; count += times ; if ( count >= k ) { ans = String . fromCharCode ( C ) ; break ; } } return ans ; } function updateTree ( str , pos , s ) { let index = pos ; update_BITree ( index , str [ index ] , - 1 ) ; str = str . substring ( 0 , index ) + s + str . substring ( index + 1 ) ; update_BITree ( index , s , 1 ) ; } let str = " " ; N = str . length ; str = ' ' + str ; let Q = 3 ; buildTree ( str ) ; document . write ( printCharacter ( str , 1 , 2 , 2 ) + " " ) ; updateTree ( str , 4 , ' ' ) ; document . write ( printCharacter ( str , 1 , 5 , 4 ) + " " ) ;