Queries on substring palindrome formation | Javascript program to Queries on substring palindrome formation . ; Return the frequency of the character in the i - th prefix . ; Updating the BIT ; Query to update the character in the string . ; 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 string S . ; Checking if frequency of character is even or odd . ; Creating the Binary Index Tree of all aphabet ; Driver code
let max = 1000 ; function getFrequency ( tree , idx , i ) { let sum = 0 ; while ( idx > 0 ) { sum += tree [ idx ] [ i ] ; idx -= ( idx & - idx ) ; } return sum ; } function update ( tree , idx , val , i ) { while ( idx <= max ) { tree [ idx ] [ i ] += val ; idx += ( idx & - idx ) ; } } function qType1 ( tree , l , x , str ) { update ( tree , l , - 1 , str [ l - 1 ] . charCodeAt ( 0 ) - 97 + 1 ) ; str [ l - 1 ] = x ; update ( tree , l , 1 , str [ l - 1 ] . charCodeAt ( 0 ) - 97 + 1 ) ; } function qType2 ( tree , l , r , str ) { let count = 0 ; for ( let i = 1 ; i <= 26 ; i ++ ) { if ( l == 1 ) { if ( getFrequency ( tree , r , i ) % 2 == 1 ) count ++ ; } else { if ( ( getFrequency ( tree , r , i ) - getFrequency ( tree , l - 1 , i ) ) % 2 == 1 ) count ++ ; } } if ( count <= 1 ) document . write ( " " ) ; else document . write ( " " ) ; } function buildBIT ( tree , str , n ) { for ( let i = 0 ; i < n ; i ++ ) update ( tree , i + 1 , 1 , str [ i ] . charCodeAt ( 0 ) - 97 + 1 ) ; } let str = " " . split ( " " ) ; let n = str . length ; let tree = new Array ( max ) ; for ( let i = 0 ; i < tree . length ; i ++ ) { tree [ i ] = new Array ( 27 ) ; for ( let j = 0 ; j < tree [ i ] . length ; j ++ ) { tree [ i ] [ j ] = 0 ; } } buildBIT ( tree , str , n ) ; qType1 ( tree , 4 , ' ' , str ) ; qType2 ( tree , 1 , 4 , str ) ; qType2 ( tree , 2 , 3 , str ) ; qType1 ( tree , 10 , ' ' , str ) ; qType2 ( tree , 10 , 11 , str ) ;