1.
Introduction
2.
Solution Approach
2.1.
Algorithm
2.2.
C++ code:
2.3.
Algorithm Complexity:
2.4.
3.
Key takeaways
Last Updated: Mar 27, 2024

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

Riya
0 upvote

## 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.

## 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.

### 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).

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).

## Key takeaways

This article discussed the problem  "Queries to evaluate the given equation in a range [L, R]," the solution approach to this problem,  its C++ implementation, and its time and space complexity. If you want to solve similar problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.