I have this problem I'm curious about where I have an Array and I need to compute the Sum of this function:

Arr[L] (Arr[L] ^ Arr[L 1]) ... (Arr[L] ^ Arr[L 1] ^ ... ^ Arr[R])

Example:

If the Array given was: [1, 2, 3, 5] and I asked what's the sum on the range [L = 1, R = 3] (assuming 1-based Index), then it'd be:

Sum = 1 (1 ^ 2) (1 ^ 2 ^ 3) = 4

In this problem, the Array, the size of the Array, and the Ranges are given. My approach for this is too slow.

What I have:

I XOR'ed each element and then summed it to a variable within the range of [L, R]. Is there any faster way to compute this if the elements in the Array are suppose... 1e18 or 1e26 larger?

#include <iostream>
#include <array>

int main (int argc, const char** argv)
{
    long long int N, L, R;
    std::cin >> N;
    
    long long int Arr[N];
    for (long long int i = 0; i < N; i  )
    {
        std::cin >> Arr[i];
    }

    std::cin >> L >> R;
        
    long long int Summation = 0, Answer = 0;    
    for (long long int i = L; i <= R; i  )
    {
        Answer = Answer ^ Arr[i - 1];
        Summation  = Answer;
    }
        
    std::cout << Summation << '\n';
    
    return 0;
}

CodePudding user response：

There are two loops in your code:

for (long long int i = 0; i < N; i  )
{
    std::cin >> Arr[i];
}

long long int Summation = 0, Answer = 0;    
for (long long int i = L; i <= R; i  )
{
    Answer = Answer ^ Arr[i - 1];
    Summation  = Answer;
}

The second loop is smaller, and only does two operations (^= and ). These are native CPU instructions; this will be memory bound on the sequential access of Arr[]. You can't speed this up. You need all elements, and it doesn't get faster than a single sequential scan. The CPU prefetcher will hit maximum memory bandwidth.

However, the killer is the first loop. Parsing digits takes many, many more operations, and the range is even larger.

CodePudding user response：

If indices are 0 based. That is L=0 implies the first element: Arr[0] is the first element in the array, then it's simply this:

int sum = 0;
int prev = 0;

for (int i = L; i <= R; i  )
{
    int current = (prev ^ Arr[i]);
    sum  = current;
    prev = current;
}

If it's 1 based, where L=1 is really Arr[0], then it's a quick adjustment:

int sum = 0;
int prev = 0;

for (int i = L; i <= R; i  )
{
    int current = (prev ^ Arr[i-1]);
    sum  = current;
    prev = current;
}

CodePudding user response：

Changing a bit the subject by making L and R valid indices of an integer matrix ( range [0, size) ), the following function is working for me:

size_t xor_rec(size_t* array, size_t size, size_t l, size_t r) {
    if (l < 0 || r >= size || l > r) {
        return 0; // error control
    }
    if (r > l   1) {
        size_t prev_to_prev_sum = xor_rec(array, size, l, r - 2);
        size_t prev_sum = prev_to_prev_sum   (prev_to_prev_sum ^ array[r - 1]);
        return prev_sum   ((prev_sum - prev_to_prev_sum) ^ array[r]);
    }
    if (r == l   1) {
        return array[r - 1]   (array[r - 1] ^ array[r]);
    }
    if (r == l) {
        return array[r];
    }
    return 0;
}

Edit: changed int for size_t.