**Problem D** : SPIDEY

**SETTER** : lamda_cdm_10

**TESTER** :vishaaaal

**Editorialist** : lamda_cdm_10

# DIFFICULTY

Medium

# PREREQUISITES

SOS-DP , Bit Manipulation

# PROBLEM

You are given an array and you are given queries in the form [ L ,R , X ] you need to find the sum of elements in the indexes (i) of the array where i|X=X where | is bit wise OR operator. The value of X for current query is (X+PREV) where PREV is the answer of the previous query PREV=0 for first query.

# EXPLANATION

Let’s define a function F(R) which gives us the sum of values in the range [0-R] we can find the answer for this query by F(R)-F(L-1).

Let’s try to understand the implementation of F(R).

Check that the value of X can be very high but we require the bits which are at the right of MSB of (2*N) . so for each X can be take mod by (2*N) everytime.

We create the SOS dp table.

Now we go through the following conditions

- If R is less than 0 we simply return 0
- If X is less than or equal to R we simply return dp[R][20]

**Now comes the condition where X is larger than R we need to analyze the cases carefully** - We form 2 vectors that contain the binary representation of X and R+1 namely A and B respectively for each of the conditions we find the cases where the submask of X is strictly less than R+1.

What we do now is try to traverse through from the MSB of X and analyze the conditions.

For this we take a Variable pref = X and move from 0 to 20 . - if we find A[i] = 0 and B[i] = 1 that means we have to break from the loop as B is no longer the submask of A and add dp[pref][20-i] to result.
- if we find A[i] = 1 and B[i] = 1 then we add dp[pref^(1<<(20-i))][20-i] to the result , what we have done here is find all the submask such that A[i] is 0 .
- if we find A[i] = 1 and B[i] = 0 set pref^=(1<<(20-i)) because this bit needs to be 0 for A[i]

# TIME-COMPLEXITY

The time complexity is O(Q*log(N)) as we expend log(N) time to answer each query.

# CODES

## SETTER'S SOLUTION

## TESTER'S SOLUTION

Any other solution or feedback can be posted in the comments. We are always open for them .