Xor-sequence

• Time : O(1)
• Space : O(1)

c++

// prefix xor 0 ... n
long helper(long n) {
    auto m = n % 8;
    if(m <= 1) return n;
    if(m <= 3) return 2;
    if(m <= 5) return n + 2;
    return 0;
}

long xorSequence(long l, long r) {
    return helper(r) ^ helper(l - 1);
}