Recently I was trying the question Maximum Xor Query of codechef. I decided to go for the editorial there I found to build a segment tree with each node being a trie. I am not able to understand the following piece of code that how they are finding maximum xor. Can anyone help me out??
int solve(vi &vec, int v) {
/*cout<<"VEC : ";
for(int i = 0; i < vec.size(); i++)
{
cout<<vec[i]<<' ';
}
cout<<'\n';*/
int l = 0; int r = vec.size() - 1;
int cur = 0;
int ans = 0;
//cout<<l<<" "<<r<<endl;
for(int i = 24 - 1; i >= 0; i--)
{
if(v&(1<<i))
{
int x = lower_bound(vec.begin()+l, vec.begin()+r+1, cur+(1<<i)) - vec.begin();
cout<<1<<" "<<x<<endl;
if(l<=x-1)
{
r = min(r, x-1);
ans+=(1<<i);
}
else
{
cur+=(1<<i);
}
}
else
{
int x = lower_bound(vec.begin()+l, vec.begin()+r+1, cur+(1<<i)) - vec.begin();
// cout<<0<<" "<<x<<" "<<i<<endl;
if(r>=x)
{
l = max(x,l);
ans+=(1<<i);
cur+=(1<<i);
}
}
}
return ans;
}