I am trying to solve the following problem at HackerRank:
XOR-Sequence
An array, \$A\$, is defined as follows:
- \$A_0 = 0\$
- \$A_x = A_{x-1} \oplus x\$ for \$x>0\$, where \$\oplus\$ is the symbol for XOR
You must answer \$Q\$ questions. Each \$i^{th}\$ question is in the form \$L_i\ R_i\$, and the answer is \$A_{L_i} \oplus A_{L_i+1} \oplus \ldots \oplus A_{R_i-1} \oplus A_{R_i}\$ (the Xor-Sum of segment \$[Li,Ri]\$).
Print the answer to each question.
Input Format
The first line contains \$Q\$ (the number of questions).
The \$Q\$ subsequent lines each contain two space separated integers, \$L\$ and \$R\$, respectively. Line \$i\$ contains \$L_i\$ and \$R_i\$.Constraints
\$1 \le Q \le 10^5\$
\$1 \le L_i \le R_i \le 10^{15}\$
My code is correct, but it's slow. It really starts slowing down once I reach numbers like 269 million for the array index. The max array index can be 1015, so it will be really slow. What things can I do to increase the speed?
#include <iostream>
int main() {
int N;
int64_t f_index, l_index;
std::cin >> N;
for (int i = 0; i < N; ++i) {
std::cin >> f_index >> l_index;
int64_t sum = 0;
int64_t temp;
for (int64_t index = f_index; index <= l_index; ++index) {
if (index%4 == 0) {
temp = sum^index;
sum = temp;
} else if (index%4 == 1) {
temp = sum^1;
sum = temp;
} else if (index%4 == 2) {
temp = sum^(index + 1);
sum = temp;
} else if (index%4 == 3) {
temp = sum^0;
sum = temp;
}
}
std::cout << sum << std::endl;
}
return 0;
}