XOR of range [L - R] inclusive for multiple queries

Hi, I have a doubt about how we can find the xor of all the values of an array within range [L - R] inclusive for multiple queries of the form [L - R] efficiently.
Note : 1 <= L < R <= 10^18

using namespace std ;

int Q ;
long long int L , R , DP[65][2] , A[65][2];
void pre(){
    DP[0][0] = DP[0][1] = 1 ;
    for(int i=1;i<=64;i++){
        DP[i][0] = (DP[i-1][0]+DP[i-1][1]) ;
        DP[i][1] = (DP[i-1][0]+DP[i-1][1]) ;

void solve(){
    long long sum = 0 ;
    for(int i=63;i>=0;i--){
        A[i][0] += sum ;
        if(L & (1LL <=0;i--){
        A[i][1] += sum ;
        if(R & (1LL <=0;i--){
        A[i][1] -= A[i][0] ;
        A[i][1] %= 2 ;
            sum += (1LL << i) ;
    cout << sum <> Q ;
    while(Q -- ){
        cin >> L >>  R ;
        solve() ;
    return 0 ;

I thought over this problem and find a simple solution using Dynammic Programming O(log(10^18)). As you know that the XOR Operation is independent for all bits participating in the operaton. Therefore for each bit we can count the number of numbers having set in the range L to R.

This code is not tested well but it should work as the idea is correct :).


btw can i have link to the above problem :slight_smile: .

Problem link : http://codeforces.com/contest/15/problem/C
There is a nice trick to find the xor of all the numbers within range [L-R].
btw thanks, just learned 2 new approaches for the same task :slight_smile:

It will be great if you share your approach here. I will learn something new.

i submitted this code on the link provided by you and got WA.This is because i forget to add a memset statement in my solution. add it and it works very fine :slight_smile: . Thanks for asking this

Sorry for the late reply, but second approach is well explained in its editorial. You can have a look at