text: Number of triplets in array having subarray xor equal | C ++ trie based program to find the Number of triplets in array having subarray xor equal ; maximum number of bits in an integer <= 1e9 ; Structure of a Trie Node ; [ 0 ] index is bit 0 and [ 1 ] index is bit 1 ; Sum of indexes inserted at at a node ; Number of indexes inserted at a node ; Constructor to initialize a newly created node ; Function to insert curr_xor into the trie ; Iterate from the 31 st bit to the 0 th bit of curr_xor number ; Check if the current bit is set or not ; If this node isn 't already  present in the trie structure  insert it into the trie. ; Increase the sum of indexes by the current index value ; Increase the number of indexes by 1 ; Function to check if curr_xor is present in trie or not ; Iterate from the 31 st bit to the 0 th bit of curr_xor number ; Check if the current bit is set or not ; If this node isn 't already  present in the trie structure  that means no sub array till  current index has 0 xor so  return 0 ; Calculate the number of index inserted at final node ; Calculate the sum of index inserted at final node ; Function to return the count of valid triplets ; To store cumulative xor ; The root of the trie ; Insert the curr_xor in the trie ; Update the cumulative xor ; Check if the cumulative xor is present in the trie or not if present then add ( sz * index ) - sum ; Driver Code ; Given array
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define lg  31 NEW_LINE struct TrieNode { TrieNode * children [ 2 ] ; int sum_of_indexes ; int number_of_indexes ; TrieNode ( ) { this -> children [ 0 ] = nullptr ; this -> children [ 1 ] = nullptr ; this -> sum_of_indexes = 0 ; this -> number_of_indexes = 0 ; } } ; void insert ( TrieNode * node , int num , int index ) { for ( int bits = lg ; bits >= 0 ; bits -- ) { int curr_bit = ( num >> bits ) & 1 ; if ( node -> children [ curr_bit ] == nullptr ) { node -> children [ curr_bit ] = new TrieNode ( ) ; } node = node -> children [ curr_bit ] ; } node -> sum_of_indexes += index ; node -> number_of_indexes ++ ; } int query ( TrieNode * node , int num , int index ) { for ( int bits = lg ; bits >= 0 ; bits -- ) { int curr_bit = ( num >> bits ) & 1 ; if ( node -> children [ curr_bit ] == nullptr ) { return 0 ; } node = node -> children [ curr_bit ] ; } int sz = node -> number_of_indexes ; int sum = node -> sum_of_indexes ; int ans = ( sz * index ) - ( sum ) ; return ans ; } int no_of_triplets ( int arr [ ] , int n ) { int curr_xor = 0 ; int number_of_triplets = 0 ; TrieNode * root = new TrieNode ( ) ; for ( int i = 0 ; i < n ; i ++ ) { int x = arr [ i ] ; insert ( root , curr_xor , i ) ; curr_xor ^= x ; number_of_triplets += query ( root , curr_xor , i ) ; } return number_of_triplets ; } int main ( ) { int arr [ ] = { 5 , 2 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << no_of_triplets ( arr , n ) ; return 0 ; }