XOR of elements in a given range with updates using Fenwick Tree | Java Program to find XOR of elements in given range [ L , R ] . ; 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
import java . util . * ; class GFG { static int getXOR ( int BITree [ ] , int index ) { int ans = 0 ; index += 1 ; while ( index > 0 ) { ans ^= BITree [ index ] ; index -= index & ( - index ) ; } return ans ; } static void updateBIT ( int BITree [ ] , int n , int index , int val ) { index = index + 1 ; while ( index <= n ) { BITree [ index ] ^= val ; index += index & ( - index ) ; } } static int [ ] constructBITree ( int arr [ ] , int n ) { int [ ] BITree = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) updateBIT ( BITree , n , i , arr [ i ] ) ; return BITree ; } static int rangeXor ( int BITree [ ] , int l , int r ) { return getXOR ( BITree , r ) ^ getXOR ( BITree , l - 1 ) ; } public static void main ( String [ ] args ) { int A [ ] = { 2 , 1 , 1 , 3 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ; int n = A . length ; int [ ] [ ] q = { { 1 , 0 , 9 } , { 2 , 3 , 6 } , { 2 , 5 , 5 } , { 2 , 8 , 1 } , { 1 , 0 , 9 } } ; int [ ] BITree = constructBITree ( A , n ) ; for ( int i = 0 ; i < q . length ; i ++ ) { int id = q [ i ] [ 0 ] ; if ( id == 1 ) { int L = q [ i ] [ 1 ] ; int R = q [ i ] [ 2 ] ; System . out . print ( " XOR ▁ of ▁ elements ▁ " + " in ▁ given ▁ range ▁ is ▁ " + rangeXor ( BITree , L , R ) + "NEW_LINE"); } else { int idx = q [ i ] [ 1 ] ; int val = q [ i ] [ 2 ] ; A [ idx ] ^= val ; updateBIT ( BITree , n , idx , val ) ; } } } }