XOR of elements in a given range with updates using Fenwick Tree | Returns XOR of arr [ 0. . index ] . This function assumes that the array is preprocessed and partial XORs of array elements are stored in BITree [ ] . ; Traverse ancestors of BITree [ index ] ; XOR current element of BIT to ans ; Update index to that of the parent node in getXor ( ) view by subtracting LSB ( Least Significant Bit ) ; Updates the Binary Index Tree by replacing all ancestors of index by their respective XOR with val ; Traverse all ancestors and XOR with ' val ' . ; XOR ' val ' to current node of BIT ; Update index to that of the parent node in updateBit ( ) view by adding LSB ( Least Significant Bit ) ; Constructs and returns a Binary Indexed Tree for the given array ; Create and initialize the Binary Indexed Tree ; Store the actual values in BITree [ ] using update ( ) ; Driver Code ; Create the Binary Indexed Tree ; Solve each query in Q ; Update the values of all ancestors of idx
def getXOR ( BITree , index ) : NEW_LINE INDENT ans = 0 NEW_LINE index += 1 NEW_LINE while ( index > 0 ) : NEW_LINE INDENT ans ^= BITree [ index ] NEW_LINE index -= index & ( - index ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def updateBIT ( BITree , n , index , val ) : NEW_LINE INDENT index = index + 1 NEW_LINE while ( index <= n ) : NEW_LINE INDENT BITree [ index ] ^= val NEW_LINE index += index & ( - index ) NEW_LINE DEDENT DEDENT def constructBITree ( arr , n ) : NEW_LINE INDENT BITree = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT updateBIT ( BITree , n , i , arr [ i ] ) NEW_LINE DEDENT return BITree NEW_LINE DEDENT def rangeXor ( BITree , l , r ) : NEW_LINE INDENT return ( getXOR ( BITree , r ) ^ getXOR ( BITree , l - 1 ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 2 , 1 , 1 , 3 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] NEW_LINE n = len ( A ) NEW_LINE q = [ [ 1 , 0 , 9 ] , [ 2 , 3 , 6 ] , [ 2 , 5 , 5 ] , [ 2 , 8 , 1 ] , [ 1 , 0 , 9 ] ] NEW_LINE BITree = constructBITree ( A , n ) NEW_LINE for i in range ( len ( q ) ) : NEW_LINE INDENT id = q [ i ] [ 0 ] NEW_LINE if ( id == 1 ) : NEW_LINE INDENT L = q [ i ] [ 1 ] NEW_LINE R = q [ i ] [ 2 ] NEW_LINE print ( " XOR ▁ of ▁ elements ▁ in ▁ " " given ▁ range ▁ is ▁ " , rangeXor ( BITree , L , R ) ) NEW_LINE DEDENT else : NEW_LINE INDENT idx = q [ i ] [ 1 ] NEW_LINE val = q [ i ] [ 2 ] NEW_LINE A [ idx ] ^= val NEW_LINE updateBIT ( BITree , n , idx , val ) NEW_LINE DEDENT DEDENT DEDENT