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 ; Number of queries ; Construct the Fenwick Tree
maxn = 100005 NEW_LINE BITree = [ [ 0 for x in range ( maxn ) ] for y in range ( 26 ) ] NEW_LINE N = 0 NEW_LINE def update_BITree ( index , C , val ) : NEW_LINE INDENT while ( index <= N ) : NEW_LINE INDENT BITree [ ord ( C ) - ord ( ' a ' ) ] [ index ] += val NEW_LINE index += ( index & - index ) NEW_LINE DEDENT DEDENT def sum_BITree ( index , C ) : NEW_LINE INDENT s = 0 NEW_LINE while ( index ) : NEW_LINE INDENT s += BITree [ ord ( C ) - ord ( ' a ' ) ] [ index ] NEW_LINE index -= ( index & - index ) NEW_LINE DEDENT return s NEW_LINE DEDENT def buildTree ( st ) : NEW_LINE INDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT update_BITree ( i , st [ i ] , 1 ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def printCharacter ( st , l , r , k ) : NEW_LINE INDENT count = 0 NEW_LINE for C in range ( ord ( ' z ' ) , ord ( ' a ' ) - 1 , - 1 ) : NEW_LINE INDENT times = ( sum_BITree ( r , chr ( C ) ) - sum_BITree ( l - 1 , chr ( C ) ) ) NEW_LINE count += times NEW_LINE if ( count >= k ) : NEW_LINE INDENT ans = chr ( C ) NEW_LINE break NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def updateTree ( st , pos , s ) : NEW_LINE INDENT index = pos ; NEW_LINE update_BITree ( index , st [ index ] , - 1 ) NEW_LINE st . replace ( st [ index ] , s , 1 ) NEW_LINE update_BITree ( index , s , 1 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " abcddef " NEW_LINE N = len ( st ) NEW_LINE Q = 3 NEW_LINE buildTree ( st ) NEW_LINE print ( printCharacter ( st , 1 , 2 , 2 ) ) NEW_LINE updateTree ( st , 4 , ' g ' ) NEW_LINE print ( printCharacter ( st , 1 , 5 , 4 ) ) NEW_LINE DEDENT