Queries to Evaluate the given Expression in a range [L, R]

Introduction 

This blog will discuss the problem "Queries to evaluate the given expression in a range [L, R]."

In this problem, we will be given an array containing 'N' integers and 'q' queries of the form {L, R}, where 0 <= L < R <= N-1 and we have to evaluate the value of the following expression for each query:

XL | XL+1 | ……| XR-1

where  Xi = ( arr[i] ^ arr[i+1] ) | ( arr[i] ~ arr[i+1] ) ,

              “|” =  Binary OR operation

              “~” = Binary XNOR operation

              “^” = Binary XOR operation

Let's understand the problem with an example:

Suppose N = 5 and given array of integers is:

arr = { 6, 1, 4, 0, 3 }

And q = 3 and given queries of the form {L, R} are:

queries[][] = { { 0, 3 }, { 1, 2 }, {3, 4} }

We have to evaluate the above given expression for these three queries:

1st query: {0, 3}

Value of expression for this query = X0 | X1 | X2

Here, 

X0 = ( arr[0] ^ arr[1] ) | ( arr[0] ~ arr[1] ) = ( 6 ^ 1 ) | ( 6 ~ 1 ) = 7 | 0 = 7

X1 = ( arr[1] ^ arr[2] ) | ( arr[1] ~ arr[2] ) = ( 1 ^ 4 ) | ( 1 ~ 4 ) = 5 | 2 = 7

X2 = ( arr[2] ^ arr[3] ) | ( arr[2] ~ arr[3] ) = ( 4 ^ 0 ) | ( 4 ~ 0 ) = 4 | 3 = 7

So, value of expression for the query {0, 3} = X0 | X1 | X2 = 7 | 7 | 7 = 7

Similarly, we can evaluate the expression for other queries.

Now that we understand the problem let's discuss the approach to solve it in the next section.

Also read, Euclid GCD Algorithm

Solution Approach

This section will discuss the approach to solve the problem "Queries to evaluate the given expression in a range [L, R]."  

A simple approach is to traverse the array from [L, R-1] for each query and calculate Ki where L <= i < R, and finally evaluate the value of the given expression for each query using the values of Ki. 

An efficient approach to solve this problem is to use a segment tree. 

We know that the result of “arr[i] ^ arr[i+1]” will have those set bits only which is either set in arr[i] or in arr[i+1], and the result of “arr[i] ~ arr[i+1]” will have those set bits only which is either set in both arr[i] and arr[i+1] or not set in both arr[i] and arr[i+1]. And, finally taking OR of these two operations will set all the bits up to the largest of the maximum significant bit of arr[i] and maximum significant bit of arr[i+1]. Therefore the approach is to find the largest number between L and R for each query and set all its bits to get the answer for that query. To efficiently calculate the largest number between L and R for each query, we will use a segment tree.

Algorithm

Step 1. Create a function "evaluateExpression()" to find the answer of the queries to evaluate the given Expression in a range [L, R], which will accept the following inputs:

1. n - Number of integers in the given array
2. arr - Given array of integers
3. q - Number of queries
4. queries[][] - Queries of the form {L,R} to evaluate the expression

Step 2. Inside the function "evaluateExpression()," first call the function to construct a segment tree using the given array of integers. Write a function "buildSegmentTree()," which will take input an array of integers and its size and construct a segment tree. Inside the function "buildSegmentTree()," calculate the height and maximum size of the segment tree and allocate memory for an array of size equal to the maximum size of the segment tree. Then call a recursive function to build the segment tree, which will get the middle element and build the left and right subtree of the segment tree recursively.

Step 3. After constructing the segment tree inside the function "evaluateExpression()," create a vector 'ans' to store the value of the given expression for each query. Iterate through the "queries[][]" vector and call the function "solveQuery()" to get the answer for each query and store it into the 'ans' vector.

Step 4. Write a function "solveQuery()," which takes the pointer to the segment tree, size of the array, and L and R of the query and returns the value of the expression for that query. Inside the function, get the maximum element between L and R using the segment tree and set all its bits to get the answer.

Step 5. Finally, after evaluating the expression for each query and storing it into the 'ans' vector, return the 'ans' vector.

C++ code:

// C++ Program to solve the queries to Evaluate the given Expression in a range [L, R]
#include <bits/stdc++.h>
using namespace std;


//Recursive function to get the maximum element between l and r
int recurGetMaxElement(int* segmentTree, int start, int end, int l, int r, int node)
{

	// If the segment of this node lies completely within the given range
	if (l <= start && r >= end) {
		return segmentTree[node];
	}

	// If the segment of this node lies outside the given range
	if (end < l || start > r) {
		return -1;
	}


	// If segment of this node lies partially in the given range
	int mid = start + (end - start)/2;

	// Call the function recursively to get the maximum from the left subtree
	int left_max = recurGetMaxElement(segmentTree, start, mid, l, r, 2 * node + 1);
    	
	// Call the function recursively to get the maximum from the right subtree
	int right_max = recurGetMaxElement(segmentTree, mid + 1, end, l, r, 2 * node + 2);

	// Return the maximum of left_max and right_max
	return max(left_max, right_max);
}


// Function to return the maximum in the range from [l, r]
int getMaxElement(int* segmentTree, int n, int l, int r)
{

	// If given range is not suitable
	if (l < 0 || r > n - 1 || l > r) {
		return -1;
	}


	// Call the recursive function to get the maximum element between l and r
	return recurGetMaxElement(segmentTree, 0, n - 1, l, r, 0);
}


// Recursive function to construct Segment Tree for the subarray [start..end]
int recurBuildSegmentTree(int* segmentTree, int arr[], int start, int end, int si)
{

	// If there is a single element in the subarray
	if (start == end) 
	{
		segmentTree[si] = arr[start];
		return arr[start];
	}

	// Else get the middle element then recursively call the function to create the left and right subtree
	int middle = start + (end - start)/2;


	// For left subtree
	int left = recurBuildSegmentTree(segmentTree, arr, start, middle, si * 2 + 1);

	// For right subtree
	int right = recurBuildSegmentTree(segmentTree, arr, middle + 1, end, si * 2 + 2);

	segmentTree[si] = max(left, right);


	return segmentTree[si];
}


// Function for constructing a Segment Tree from a given array of integers
int* buildSegmentTree(int arr[], int n)
{

	// Calculate the height of the segment tree
	int x = (int)(ceil(log2(n)));


	// Calculate the maximum size of Segment Tree
	int max_size = 2 * (int)pow(2, x) - 1;


	// Allocating memory
	int* segmentTree = new int[max_size];


	// Call a recursive function to fill the allocated memory recursively
	recurBuildSegmentTree(segmentTree, arr, 0, n - 1, 0);


	// Return the constructed Segment Tree
	return segmentTree;
}


// Function to return the value of Expression for a query {L,R}
int solveQuery(int* segmentTree, int n, int L, int R)
{

	// Call the function to find the maximum element between L and R using Segment Tree
	int maxElement = getMaxElement(segmentTree, n, L, R);

	bool flag = false;
	for (int i = 30; i >= 0; i--) 
	{
		if ((maxElement & (1 << i)) != 0) {
			flag = true;
		}

		if (!flag) {
			continue;
		}

		maxElement = maxElement | (1 << i);
	}

	return maxElement;
}


// Function to return answer of the queries to Evaluate the given Expression in a range [L, R]
vector<int> evaluateExpression(int arr[], int n, vector<vector<int>> queries, int q)
{

	// Construct a Segment Tree from the given array
	int* segmentTree = buildSegmentTree(arr, n);

	// Vector to store the value of the given expression for each query
	vector<int> ans;

	// Iterate through each query and solve the queries to Evaluate the given Expression in a range [L, R]
	for (int i = 0; i < q; i++) 
	{
		int L = queries[i][0];
		int R = queries[i][1];

		int val = solveQuery(segmentTree, n, L, R);


		ans.push_back(val);
	}

	return ans;
}
  
// Main Function
int main()
{

	// Number of integers in the given array
	int n =5;

	// Given array
	int arr[] = { 6, 1, 4, 0, 3 };

	// Given number of Queries
	int q = 3;

	// Given Queries
    vector<vector<int> > queries = { { 0, 3 }, { 1, 2 }, {3, 4} };
    	
	// Call the function to get the answer of the queries to Evaluate the given Expression in a range [L, R]
	vector<int> ans = evaluateExpression(arr, n, queries, q);

	for(int i=0; i<ans.size(); i++)
	{
   	cout<<ans[i]<<" ";
	}

	return 0;
}

Output:
7 7 3 

Algorithm Complexity: 

Time Complexity: O(Q * log (size of Q))

In the above program to find the answer to the queries to evaluate the given Expression in a range [L, R], we have created a segment tree that takes O(N) time, and we have called the function "solveQuery()" for each query and each "solveQuery()" function has called "getMaxElement()" function inside it which calls a recursive function that divides the problem into two halves [L, mid] and [mid+1, R] in each iteration. So, the time complexity of getting the maximum element in [L, R] is O(log(R-L)), i.e., O(log(size of query)), as [L, R] is different for different queries. Hence, the overall time complexity is O(N + Q*log(size of Q)), where 'N' is the number of elements in the given array, 'Q' is the number of queries, and 'size of Q' is the number of elements in the range [L, R] for a given query.

Space Complexity: O(N) 

In the above program to find the answer to the queries to evaluate the given Expression in a range [L, R], we have created a segment tree that takes O(N) space. So, the space complexity is O(N).

Frequently Asked Questions

1. What is a segment tree?

A segment tree is a data structure that evaluates range sum queries and updates queries efficiently. It is basically a binary tree storing segments of an array.

2. What is the time complexity of evaluating range sum queries and update queries in a segment tree?

The time complexity for both range sum query and update query in a segment tree is O(log N).