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 &lt;= 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 &lt; n; i++)
    {
        for(int j = i; j &lt; n; j++)
        {
            if(i == j)
            {
                Table[i][j] = arr[i];
            }
            else
            {
                Table[i][j] = min(arr[j], Table[i][j - 1]);
            }
        }
    }
}
int main()
{
    cin &gt;&gt; n;
    for(int i = 0; i &lt; n; i++)
    {
        cin &gt;&gt; arr[i];
    }
    make_table();
    ll sum = 0;
    cin &gt;&gt; m;
    for(int i = 0; i &lt; m; i++)
    {
        int x, y;
        cin &gt;&gt; x &gt;&gt; y;
        sum += Table[x][y];
    }
    cout &lt;&lt; sum &lt;&lt; endl;
}
```
You can use the concept of segment trees. Check this link:
https://en.wikipedia.org/wiki/Segment_tree and https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
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 &lt; n$, the overall complexity is $O(n \log n)$.