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
function getXOR ( BITree , index ) { let ans = 0 ; index += 1 ; while ( index > 0 ) { ans ^= BITree [ index ] ; index -= index & ( - index ) ; } return ans ; } function updateBIT ( BITree , n , index , val ) { index = index + 1 ; while ( index <= n ) { BITree [ index ] ^= val ; index += index & ( - index ) ; } } function constructBITree ( arr , n ) { let BITree = new Array ( n + 1 ) ; for ( let i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; for ( let i = 0 ; i < n ; i ++ ) updateBIT ( BITree , n , i , arr [ i ] ) ; return BITree ; } function rangeXor ( BITree , l , r ) { return getXOR ( BITree , r ) ^ getXOR ( BITree , l - 1 ) ; } let A = [ 2 , 1 , 1 , 3 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] ; let n = A . length ; let q = [ [ 1 , 0 , 9 ] , [ 2 , 3 , 6 ] , [ 2 , 5 , 5 ] , [ 2 , 8 , 1 ] , [ 1 , 0 , 9 ] ] ; let BITree = constructBITree ( A , n ) ; for ( let i = 0 ; i < q . length ; i ++ ) { let id = q [ i ] [ 0 ] ; if ( id == 1 ) { let L = q [ i ] [ 1 ] ; let R = q [ i ] [ 2 ] ; document . write ( " " + " " + rangeXor ( BITree , L , R ) + " " ) ; } else { let idx = q [ i ] [ 1 ] ; let val = q [ i ] [ 2 ] ; A [ idx ] ^= val ; updateBIT ( BITree , n , idx , val ) ; } }