Do we need to solve this from segment tree? If yes then how to approach the problem?
Is it a question of segment tree?
yes @raj.verma5454 this question can be attempted using segmented tree as well
We build a segment tree of given array such that array elements are at leaves and internal nodes store XOR of leaves covered under them.
in order to refer to the code
it is just similar to building a segment tree with internal nodes as xor and extract result to all queries afterwards
Question statement is little confusing. The link shared by you gets clear input like initial array, then update the array at some position. Then find the xor of given range. And in this question We have to find Y in L & R which gives max xor with X , for this we have to construct segment tree according to every 1 query. like I store the max xor value with x in given range . And if another query comes I need to change the whole tree , and it is not update.
As given in the question we get input one by one. So how we can construct segment tree? In starting We have to know the whole array for making tree. And in the given input we get like we need to update the segment tree.
no u construct the tree on go.
and for query where update is required u call the update function
u can have an idea about how these type of q can be done from the following code
I have solved maximum xor subarray with this approach. https://ide.codingblocks.com/s/261285 . But I couldn’t understand why vector has been used while inserting . And what is the use of binary search range? You said I can construct segment tree on go , How to do that?
with the code provided above i just intended to tell u how to handle the 0 and 1 query case
U can read the editorial of the question
https://hack.codingblocks.com/app/contests/1128/932/problem
it similar to the one u used
Yeah I need help with the coding part. And one more thing , What is the use of vector array while inserting elements in the trie?
One more thing , please explain the working of binarysearchrange function
Actually I am not able to understand the problem fully. LIke If we need to find the the element in the range , Then why we take input of 0 query. Range is given L to R , which doesn’t belong to our initial input. Then what is the use of those inputs?
see,
the value of L , r always range from 1 to size of array
we need to find a value from the array from L-1 to R-1 which can generate max XOR with given X
it keeps a track of all digits which have j th bit set in it .
brro its basically asking u for an answer from the range L , R from the array element
please read the code it is well commented
How I got the question right. I am bit confuse regarding L and R . I think statement given for query one has to be little more specific like L & R both would be in array’s range and also it is not given in the constraint.
That was “now I got the question right”
1 Like
One more doubt. See code from line no 68 to 76 else condition. For finding max xor we move in opposite direction and include the xor value in ans. But in this condition we have checked our jth bit is set and find if it’s left child exist or not , if yes then we have to include it in our ans , but you have included the ans in second condition, you have checked if my jth bit is set and it’s left child!=NULL && findinrange() then we simply go temp=temp->left, instead of including it in our ans. But in else part you have included in the ans. Why is that?
while building the trie data structure we had 1 for the right side and 0 for the left side
so
only when we are travelling to the right side of a node we update the XOR value
since ussi side bit set hogi
and doing xor with 0 ( ie to the left) will not lead to update
I am sharing your code with comments form line 68 to 79 . And I am sharing a code of find max pair in an array which gives you an idea what I am saying. 1) Your code with comment https://ide.codingblocks.com/s/263157 2) Max xor pair https://ide.codingblocks.com/s/263139
jth bit x mein already set hai , to xor maximize karne ke liye y ki jth bit off honi chaiye.
agar hume l - r mein koi aise value milti hai jiski jth bit off ho to hum left move kar jayenge
otherwise hame y meth jth bit set karna padega
I think there is a bit confusion. For the given test case from range 1-4 , we have four elements 3,5,10,6 and max value of max_xor in this range is 10^6=12 , then how it is giving 10 in the output. If you are saying we have to find a number between L to R which is (1,4) for the given range you have passed (0,3) in which there are (0,1,2,3) and finding xor with any no does not lead to xor value of 10. Just explain the test case and the elements in the given range then verify it manually.
hume max_xor ki value nhi btanai
hume btana h vo element jise max_xor produce ho rha h
like 10^6 se max araha h
so 10 display karana h