Calculate sum of multiple series within array 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&lt;=L&lt;=R&lt;=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 &lt;iostream&gt;

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 &lt;= second)
    {
        sum += (long long)residues[pos - first] * numbers[pos];
        sum %= 1000000007;
        pos++;
    }
    return sum;
}

int main()
{
    residues[0] = 1;
    int n, q ;
    cin &gt;&gt; n &gt;&gt; q;
    for(int i = 0; i &lt; n; i++)
    {
        cin &gt;&gt; numbers[i];
        findResidues(i + 1);
    }
    for(int i = 0; i &lt; q; i++)
    {
        cin &gt;&gt; pairs[i][0] &gt;&gt; pairs[i][1];
        cout &lt;&lt; sumBetween(pairs[i][0] - 1, pairs[i][1] - 1) &lt;&lt; endl;
    }
    return 0;
}
int pairs[MAXN][2]; wastes memory. You don't need to read all the queries at once:
  for(int i = 0; i &lt; q; i++)
  {
      cin &gt;&gt; L &gt;&gt; R;
      cout &lt;&lt; sumBetween(L - 1, R - 1) &lt;&lt; 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.