# Calculate the sum of all sub-arrays with given indices

I am new to Algorithms and Competitive Coding. I have a problem as follow:

For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic Programming or any other way which can run in less than O(nlogn) or even O(n) and the limit memory is 256 Mb.

Initially, I have a simple approach to dynamic programming as follows: I just create a table size nxn and fill it with numbers that represent the minimum element from the index I to index j (i <= j). After that, I refer to the given indexes (ik and jk) on the table and add them up.

However, as submitting the code as the previous approach, I get 3 cases of wrong answers and even runtime errors. The runtime error is due to the input constraint: up to 10^6 elements which cause the exceed of memory (10^6 * 10^6 = 10^12, which is very large). I also get accepted status on 3 tests however, the number of wrong answers makes me quite confused. I really need your help to check and update the algorithms.

Sample test case:

Input:

16

2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4

4

1 5

0 9

1 15

6 10

Output:

6

void make_table()
{
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
if(i == j)
{
Table[i][j] = arr[i];
}
else
{
Table[i][j] = min(arr[j], Table[i][j - 1]);
}
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
make_table();
ll sum = 0;
cin >> m;
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
sum += Table[x][y];
}
cout << sum << endl;
}
$$$$
`
• Please credit the original source of all copied material - see cs.stackexchange.com/help/referencing
– D.W.
Dec 12 '20 at 18:45
• Requests for us to check your code are off-topic here. Please remove all code and replace it with concise pseudocode.
– D.W.
Dec 12 '20 at 18:45
• – D.W.
Dec 12 '20 at 18:47

The above link works for finding the sum of all the elements in a given range [i,j]. However, you can use the same approach to find the minimum element in the range [i,j] in $$O(\log n)$$ time. The idea is that you can break the range [i,j] into $$O(\log n)$$ smaller ranges, and for each of these ranges you already know their minimum values via some binary tree (built during pre-processing step). Thus, you can take the minimum over all these small ranges, and it will give the overall minimum in the range [i,j] in $$O(\log n)$$ time.
Building the binary tree comes under the pre-processing step and it will only take $$O(n)$$ time.
Also, there are $$m$$ queries and each query takes $$O(\log n)$$ time. The overall time complexity would be $$O(n + m \log n)$$. Since $$m < n$$, the overall complexity is $$O(n \log n)$$.