Queries on substring palindrome formation | Python3 program to Queries on substr1ing palindrome formation . ; Return the frequency of the character in the i - th prefix . ; Updating the BIT ; Query to update the character in the str1ing . ; Adding - 1 at L position ; Updating the character ; Adding + 1 at R position ; Query to find if rearrangement of character in range L ... R can form palindrome ; Checking on the first character of the str1ing S . ; Checking if frequency of character is even or odd . ; Creating the Binary Index Tree of all aphabet ; Driver code
max = 1000 ; NEW_LINE def getFrequency ( tree , idx , i ) : NEW_LINE INDENT sum = 0 ; NEW_LINE while ( idx > 0 ) : NEW_LINE INDENT sum += tree [ idx ] [ i ] ; NEW_LINE idx -= ( idx & - idx ) ; NEW_LINE DEDENT return sum ; NEW_LINE DEDENT def update ( tree , idx , val , i ) : NEW_LINE INDENT while ( idx <= max ) : NEW_LINE INDENT tree [ idx ] [ i ] += val ; NEW_LINE idx += ( idx & - idx ) ; NEW_LINE DEDENT DEDENT def qType1 ( tree , l , x , str1 ) : NEW_LINE INDENT update ( tree , l , - 1 , ord ( str1 [ l - 1 ] ) - 97 + 1 ) ; NEW_LINE list1 = list ( str1 ) NEW_LINE list1 [ l - 1 ] = x ; NEW_LINE str1 = ' ' . join ( list1 ) ; NEW_LINE update ( tree , l , 1 , ord ( str1 [ l - 1 ] ) - 97 + 1 ) ; NEW_LINE DEDENT def qType2 ( tree , l , r , str1 ) : NEW_LINE INDENT count = 0 ; NEW_LINE for i in range ( 1 , 27 ) : NEW_LINE INDENT if ( l == 1 ) : NEW_LINE INDENT if ( getFrequency ( tree , r , i ) % 2 == 1 ) : NEW_LINE INDENT count += 1 ; NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( ( getFrequency ( tree , r , i ) - getFrequency ( tree , l - 1 , i ) ) % 2 == 1 ) : NEW_LINE INDENT count += 1 ; NEW_LINE DEDENT DEDENT DEDENT print ( " Yes " ) if ( count <= 1 ) else print ( " No " ) ; NEW_LINE DEDENT def buildBIT ( tree , str1 , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT update ( tree , i + 1 , 1 , ord ( str1 [ i ] ) - 97 + 1 ) ; NEW_LINE DEDENT DEDENT str1 = " geeksforgeeks " ; NEW_LINE n = len ( str1 ) ; NEW_LINE tree = [ [ 0 for x in range ( 27 ) ] for y in range ( max ) ] ; NEW_LINE buildBIT ( tree , str1 , n ) ; NEW_LINE qType1 ( tree , 4 , ' g ' , str1 ) ; NEW_LINE qType2 ( tree , 1 , 4 , str1 ) ; NEW_LINE qType2 ( tree , 2 , 3 , str1 ) ; NEW_LINE qType1 ( tree , 10 , ' t ' , str1 ) ; NEW_LINE qType2 ( tree , 10 , 11 , str1 ) ; NEW_LINE