Queries to calculate Bitwise AND of an array with updates | Store the number of set bits at each position ; Function to precompute the prefix count array ; Iterate over the range [ 0 , 31 ] ; Set the bit at position i if arr [ 0 ] is set at position i ; Traverse the array and take prefix sum ; Update prefixCount [ i ] [ j ] ; Function to find the Bitwise AND of all array elements ; Stores the required result ; Iterate over the range [ 0 , 31 ] ; Stores the number of set bits at position i ; If temp is N , then set ith position in the result ; Print the result ; Function to update the prefix count array in each query ; Iterate through all the bits of the current number ; Store the bit at position i in the current value and the new value ; If bit2 is set and bit1 is unset , then increase the set bits at position i by 1 ; If bit1 is set and bit2 is unset , then decrease the set bits at position i by 1 ; Function to find the bitwise AND of the array after each query ; Fill the prefix count array ; Traverse the queries ; Store the index and the new value ; Store the current element at the index ; Update the array element ; Apply the changes to the prefix count array ; Print the bitwise AND of the modified array ; Driver Code
prefixCount = [ [ 0 for x in range ( 32 ) ] for y in range ( 10000 ) ] NEW_LINE def findPrefixCount ( arr , size ) : NEW_LINE INDENT for i in range ( 32 ) : NEW_LINE INDENT prefixCount [ i ] [ 0 ] = ( ( arr [ 0 ] >> i ) & 1 ) NEW_LINE for j in range ( 1 , size ) : NEW_LINE INDENT prefixCount [ i ] [ j ] = ( ( arr [ j ] >> i ) & 1 ) NEW_LINE prefixCount [ i ] [ j ] += prefixCount [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT def arrayBitwiseAND ( size ) : NEW_LINE INDENT result = 0 NEW_LINE for i in range ( 32 ) : NEW_LINE INDENT temp = prefixCount [ i ] [ size - 1 ] NEW_LINE if ( temp == size ) : NEW_LINE INDENT result = ( result | ( 1 << i ) ) NEW_LINE DEDENT DEDENT print ( result , end = " ▁ " ) NEW_LINE DEDENT def applyQuery ( currentVal , newVal , size ) : NEW_LINE INDENT for i in range ( 32 ) : NEW_LINE INDENT bit1 = ( ( currentVal >> i ) & 1 ) NEW_LINE bit2 = ( ( newVal >> i ) & 1 ) NEW_LINE if ( bit2 > 0 and bit1 == 0 ) : NEW_LINE INDENT prefixCount [ i ] [ size - 1 ] += 1 NEW_LINE DEDENT elif ( bit1 > 0 and bit2 == 0 ) : NEW_LINE INDENT prefixCount [ i ] [ size - 1 ] -= 1 NEW_LINE DEDENT DEDENT DEDENT def findbitwiseAND ( queries , arr , N , M ) : NEW_LINE INDENT findPrefixCount ( arr , N ) NEW_LINE for i in range ( M ) : NEW_LINE INDENT id = queries [ i ] [ 0 ] NEW_LINE newVal = queries [ i ] [ 1 ] NEW_LINE currentVal = arr [ id ] NEW_LINE arr [ id ] = newVal NEW_LINE applyQuery ( currentVal , newVal , N ) NEW_LINE arrayBitwiseAND ( N ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE queries = [ [ 0 , 2 ] , [ 3 , 3 ] , [ 4 , 2 ] ] NEW_LINE N = len ( arr ) NEW_LINE M = len ( queries ) NEW_LINE findbitwiseAND ( queries , arr , N , M ) NEW_LINE DEDENT