Calculate sum of multiple series within array

Question

The exercise is as follows:

Player A will write list \$ a \$ consisting of \$ n \$ numbers. Player B will take a look at the paper. After that the A player will ask player B \$q\$ questions. Each question will be of the following form:

If I give you two \$ R \$ and \$ L \$ in \$ a \$ such that (\$ 1<=L<=R<=n\$ ), calculate the following value:

$$ 1*a[L] + 2*a[L+1] + 4*a[L+2] + ... + 2^{R-L-1}*a[R-1]+2^{R-L}*a[R] $$

Because the numbers can be really large, we need to find the residue that the result will give when divided by \$ 10^9 + 7\$.

Input is as follows:

n q
a1 a2 an
L1 R1
L2 R2
Lq Rq

The output is: on one line the result for one query.

The problem:

I need to improve performance so it is finished within 1 second. I think the problem may be because I have 2 for loops. Because the number of numbers can be up to 200,000 as well as the pairs. This means that in the worst case it has to go through the process 40,000,000,000 times.

Can someone please tell me how to improve the performance?

#include <iostream>

using namespace std;

const int MAXN = 200000;

int residues[MAXN];
int numbers[MAXN];
int pairs[MAXN][2];

void findResidues(int i)
{
    residues[i] = (residues[i - 1] * 2) % 1000000007;
}

long long int sumBetween(int first, int second)
{
    long long int sum = 0;
    int pos = first;
    while(pos <= second)
    {
        sum += (long long)residues[pos - first] * numbers[pos];
        sum %= 1000000007;
        pos++;
    }
    return sum;
}

int main()
{
    residues[0] = 1;
    int n, q ;
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        cin >> numbers[i];
        findResidues(i + 1);
    }
    for(int i = 0; i < q; i++)
    {
        cin >> pairs[i][0] >> pairs[i][1];
        cout << sumBetween(pairs[i][0] - 1, pairs[i][1] - 1) << endl;
    }
    return 0;
}

Answer 1

• int pairs[MAXN][2]; wastes memory. You don't need to read all the queries at once:

    for(int i = 0; i < q; i++)
    {
        cin >> L >> R;
        cout << sumBetween(L - 1, R - 1) << endl;
    }
  

  works equally well. Besides, the problem statement doesn't say how many queries are there; it could be way more than the size of the array.

• Your feeling that you use the wrong algorithm is well founded. Bruteforcing is almost always wrong. Look at the underlying math first. I don't want to spell out everything, just a couple of hints:

  • \$1*a_{L} + 2*a_{L+1}+ ... + 2^{R-L}*a_{R} = \dfrac{2^L*a_{L} + 2^{L+1}*a_{L+1}+... + 2^R*a_{R}}{2^L}\$

  • The numerator above is a difference of two partial sums of the \$2^n*a_{n}\$ sequence.

  • \$1000000007\$ is a prime number, so division by \$2^L\$ modulo 1000000007 is a multiplication by a multiplicative inverse of 2 modulo 1000000007 (which is trivial to find) to the same power.

  I hope it is enough to get you going in the right direction. You should be able to answer each query in constant time.

Answer 2

The code is already using symbolic constants such as MAXN, the code would be clearer if 1000000007 was a numeric constant as well.

Are you sure that first and second will always be integers you may need to make these long long as well. When using a long long there is no reason to specify int as well, the values will be integer unless otherwise indicated.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Pass the array residues into the functions findResidues() and sumBetween()

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

Use C++ Container Classes

The code is currently using old C programming style arrays, it would be better to use C++ container classes such as std::array or std::vector. Either one of these classes will allow you to use iterators which could possibly speed up the implementation.

Possibly std::vector would be a better type to use that std::array would be in this particular problem. std::vector is a variable length array. If you want to continue using MAXN as the maximum size you can reserve the memory.

Gather All the Data Before Processing the Data

Currently the program is creating the resedue information as the data is being input. Rather than breaking up calculations by getting new input first get all of the input and then process the data. Getting all the input at once should help speed up the program, and will make the algorithm easier to follow.

Break up the main() function a little more into 2 functions that get input and then functions that do the calculations.

Use size_t or Another unsigned Variable Type When Indexing Arrays or Other Indexed Variable Types

When indexing into arrays it is safer to use size_t because this is unsigned and the value can't go negative if it gets too large. Indexing by negative numbers can cause an immediate out of range exception.

Answer 3

This looks to me like a issue about efficiency, not style.

We can use prefix sums instead of brute forcing each case. (learn more here)

Create an array prefix of size n + 1. At the ith index, find whatever the sum would be for the first i numbers. For example, if the list a was a_1, a_2, a_3, ..., a_n), prefix would be 0, a_1, a_1 + 2*a_2, a_1+2*a_2+4*a_3, ....

Then, if we wanted to query from L to R, we could find prefix[R]-prefix[L-1]. As a basic example, pretend L=2, R=3. Then, the difference mentioned above would be prefix[3]-prefix[1] = 2*a_2+4*a_3, which is double of the sum that we are expecting. Afterwards, we can divide by 2^{L-1} to get what the exercise wants.

I'm a little busy right now, but I will post some code as soon as possible.

Answer 4

The std::endl flushes the buffer every time, which makes the code slower. Instead of it, you should use '\n' so the buffer only flushes when it's full.

For further reading, check out std::flush

Hope it makes your code faster!