Queries on substring palindrome formation | C ++ 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 alphabet ; Driven Program
#include <bits/stdc++.h> NEW_LINE #define max  1000 NEW_LINE using namespace std ; int getFrequency ( int tree [ max ] [ 27 ] , int idx , int i ) { int sum = 0 ; while ( idx > 0 ) { sum += tree [ idx ] [ i ] ; idx -= ( idx & - idx ) ; } return sum ; } void update ( int tree [ max ] [ 27 ] , int idx , int val , int i ) { while ( idx <= max ) { tree [ idx ] [ i ] += val ; idx += ( idx & - idx ) ; } } void qType1 ( int tree [ max ] [ 27 ] , int l , int x , char str [ ] ) { update ( tree , l , -1 , str [ l - 1 ] - 97 + 1 ) ; str [ l - 1 ] = x ; update ( tree , l , 1 , str [ l - 1 ] - 97 + 1 ) ; } void qType2 ( int tree [ max ] [ 27 ] , int l , int r , char str [ ] ) { int count = 0 ; for ( int 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 ++ ; } } ( count <= 1 ) ? ( cout << " Yes " << endl ) : ( cout << " No " << endl ) ; } void buildBIT ( int tree [ max ] [ 27 ] , char str [ ] , int n ) { memset ( tree , 0 , sizeof ( tree ) ) ; for ( int i = 0 ; i < n ; i ++ ) update ( tree , i + 1 , 1 , str [ i ] - 97 + 1 ) ; } int main ( ) { char str [ ] = " geeksforgeeks " ; int n = strlen ( str ) ; int tree [ max ] [ 27 ] ; buildBIT ( tree , str , n ) ; qType1 ( tree , 4 , ' g ' , str ) ; qType2 ( tree , 1 , 4 , str ) ; qType2 ( tree , 2 , 3 , str ) ; qType1 ( tree , 10 , ' t ' , str ) ; qType2 ( tree , 10 , 11 , str ) ; return 0 ; }