XOR of range in Segment Tree using C++

In this tute, we will discuss how to query the XOR of the given range in a segment tree using C++. Read till the end to get a clear idea of the Segment Tree. Let’s use the array representation for the Segment tree in this section. If you’ve already read Sum of range in Segment Tree using C++, you can head straight to the Segment tree section.

Before all, why use Segment trees? Let’s discuss a scenario where the segment tree can be used. Consider the scenario where an array ar[0..n-1] is given and you need to perform two operations:

Given indices strt & end, query the XOR of elements of ar[strt..end].
Given an index pos and value val, replace ar[pos] with val.

Both operations are expected to be performed many times. Let’s see three methods to approach this problem.

Method 1:

Use the given array to perform both the operations. Run through all the elements of ar[l..r] and find the XOR of them. This would take O(n) time complexity. For an update operation, access the index straight away in O(1) time.

Method 2:

Another method is to use a prefix array. This reduces the query operation to O(1) time complexity. But, since all elements in the range [pos..n-1] in the prefix array would be affected by changing the value at index pos, the update operation becomes O(n) time complexity.

These two methods become handy when only one operation is done predominantly and the other is very rarely done. What if both operations are done at equal amounts? That’s where Segment trees come handy.

Method 3:

The problem seems to be like a trade-off between query and update time complexities. But, if we use a Segment tree, both the operations can be done in O(Log₂n) time complexity. Because of this, segment trees can be used for frequent range_queries and node updates on arrays.

Dealing with XORs:

Here, we use the XOR property which tells that,

A ^ B = B ^ A
A ^ A = 0
A ^ ( B ^ A ) = B
A ^ 0 = A

XOR of range in Segment Tree:

For the XOR queries, you’ll have to find the XOR of elements in the range l & r in the array. The following algorithm is used to answer the XOR query.

Firstly, start with the root node.
If the current node’s range is entirely within the desired range, return this value.
Else, continue with the child/children containing some elements of the desired range.
Continue this till all the desired range of elements are accessed.
While tracing back to the root, take XOR for all the returned values. The value returned by the root is the XOR of the given range.

Update operation:

To update a node, the same approach used in sum segment tree is taken. Since we are dealing with XORs, after updating the node, for all intermediate nodes, let’s recalculate the two children’s XOR.

tree[idx] = tree[2*idx+1] ^ tree[idx+2];

To know more about updates in Segment trees, read Node and range updates in Segment Tree using C++

Implementation:

Following is the implementation of XOR Segment Tree. The program implements construction, range query, node update on Segment Tree.

// C++ program to show Segment Tree - XOR of range
#include<bits/stdc++.h>
using namespace std;

#define MAX 100010
int tree[MAX];
vector<int> ar;

/* Function to display elements of the Segment Tree
   level by level. */
void showSegTree(int n)
{
  int i, j, h = ceil(log2(n));
  for(i=0 ; i<=h ; ++i)
  {
    for(j=0 ; j<pow(2, i) ; ++j)
      cout<<tree[int(pow(2, i)-1 + j)]<<' ';
    cout<<endl;
  }
}

/* Function to construct the Segment Tree recursively.
   At each node, if it is not the leaf, two children are
   processed further. Otherwise, the leaf is assigned an
   array alement. strt and end are range in the array,
   idx is the index used in the segment tree */
int constSegTree(int strt, int end, int idx)
{
  // Saves tree[idx] = ar[strt] and then returns tree[idx]
  if(strt == end)
    return tree[idx] = ar[strt];

  int mid = (strt + end) / 2;
  return tree[idx] = constSegTree(strt, mid, 2*idx+1) ^
            constSegTree(mid+1, end, 2*idx+2);
}
void constSegTree(int n)
{
  constSegTree(0, n-1, 0);
}

/* Function to get the XOR of elements of array in the
   range [strt..end]. l & r are the range of current node.
   indx is the index of node in segment tree */
int getXor(int strt, int end, int l, int r, int idx)
{
  if(strt <= l && r <= end)
    return tree[idx];
  
  if(end < l || r < strt || l > r)
    return 0;
  
  int mid = (l + r) / 2;
  return getXor(strt, end, l, mid, 2*idx+1) ^
      getXor(strt, end, mid+1, r, 2*idx+2);
}
int getXor(int n, int strt, int end)
{
  return getXor(strt, end, 0, n-1, 0);
}

/* Function to update a particular node of the array in
   Segment Tree. pos is the desired index in the array.
   val is the value to be added */
void updtNode(int pos, int val, int l, int r, int idx)
{
  // pos not inside the node's range
  if(pos < l || r < pos)
    return;
  
  // Leaf node is reached
  if(l == r)
  {
    tree[idx] = val;
    return;
  }

  int mid = (l + r) / 2;
  updtNode(pos, val, l, mid, 2*idx+1);
  updtNode(pos, val, mid+1, r, 2*idx+2);

  tree[idx] = tree[2*idx+1] ^ tree[2*idx+2];
}
void updtNode(int n, int pos, int val)
{
  updtNode(pos, val, 0, n-1, 0);
}

int main()
{
  int n = 7;
  ar = {18, 17, 1, 19, 15, 11, 20};

  constSegTree(n);

  cout<<"n = 7, ar = {18, 17, 1, 19, 15, 11, 20}"<<endl;
  showSegTree(n);

  updtNode(n, 2, 3);

  cout<<"\nupdtNode(n, 2, 3):"<<endl;
  showSegTree(n);

  cout<<"\nXor of ar[1..4] = "<<getXor(n, 1, 4)<<endl;

    return 0;
}

Output:

n = 7, ar = {18, 17, 1, 19, 15, 11, 20}
1
17 16
3 18 4 20
18 17 1 19 15 11 0 0

updtNode(n, 2, 3):
16
0 16
3 23 4 20
18 17 3 19 15 11 0 0

Xor of ar[1..4] = 9

Time Complexity:

Segment Tree creation: O(n)

Range XOR query: O(Log₂n)

Node update: O(Log₂n)

Bonus: If you still find it difficult to understand about range queries, node updates in segment trees, remove all comments in the code and start tracing for your inputs.

Also, read:

Lazy Propagation in Segment Tree using C++