How to store the sum of every contigous subarray of an array?

Question

I have an array on n elements (1 <= n <= 200000). I' am suppose to find sum of every contigous subarray that can be formed from this array. I have an O(n^2) algorithm that will find all sums, but my problem is that i cant store it in any data structure as there are n(n+1)/2 elements. Thus there will be 10^10 elements which will require large space. This is the output i' am getting.

terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc Aborted (core dumped)

I guess it because of my code using too much memory. Following is my code.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define vi vector<int>
#define vli vector<lli>
#define dqi deque<int>
#define MOD 10e9+7
#define mis map<int,string>
#define msi map<string,int>
#define set0(a) memset(a,0,sizeof(a))
#define sc scanf
#define pr printf
#define rint(a) sc("%d",&a)
#define rchar(a) sc("%d",&a)
#define pb push_back
#define pf push_front
#define rstring(s) sc("%s",&s)
#define rp(a,b,c) for(int (a)=(b);(a)<(c);(a)++)
#define rpn(a)  while(a--)
int a[200010],t=0,n=0,q=0,cnt=0;
vector<long long int> b;
long long int l=0,r=0;
int main()
{
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  memset(a,0,sizeof(a));
  scanf("%d",&t);
  while(t--){
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    long long int sum=0;
    for(int i=n-1,j=1;i>=0;i--,j++){
        b.push_back(a[i]);sum=a[i];
        for(int j=i+1;j<=n-1;j++)
                b.push_back(sum+=a[j]);
    }
    //following part find the sum of elements of subarrays in a given range after sorting them
    printf("Case #%d: \n",++cnt);
    while(q--){
        scanf("%lld %lld",&l,&r);
        long long int sum=0;
        for(long long int i=l-1;i<r;i++)
            sum+=b[i];
        printf("%lld\n",sum);
    }
    b.clear();
}
return 0;
}

Is there any other way to do this. Please guide.

Answer 1

You are getting 'std::bad_alloc' because you are trying to allocate so much static memory. There is a limit for allocating the static memory, and that depends on the environment: what OS are you running this in? Is that a 16-, 32-, 64-bit memory architecture? more info.

Alternate Way

An alternate way will take O(n) time and O(n) auxiliary space. You don't need to calculate the sum of every contiguous subarray. Instead, calculate and store the sum up to the ith element from the initial array in a new array.

If the initial array (A) is [5, 3, 9, 15, 21], the new array (B) will be [5, 8, 17, 32, 53].

And whenever you need the sum of contiguous subarray [l, r] (both inclusive), where l is the left index (or the starting index) and r is the right index (or the ending index), you can get it in just O(1) time, and that sum will be equal to B[r] - B[l] + A[l].

Below is the implementation of the same.

# include <bits/stdc++.h>
using namespace std;

int main() {
    long long n; // number of elements in the array
    cin >> n;

    vector<long long> A(n), B(n); // A is the initial array (array with no modifications)
                                  // B is the calculated array (ith element of B contains sum up to the ith element of A)

    for (long long i = 0; i < n; i++) {
        cin >> A[i];

        if (i == 0) {
            B[i] = A[i];
        }
        else {
            B[i] = A[i] + B[i - 1];
        }
    }

    int q; // number of queries
    cin >> q;

    while (q--) {
        int l, r; // l is the left index (or starting index, zero based)
                  // r is the right index (or ending index, zero based)
        cin >> l >> r;

        cout << (B[r] - B[l] + A[l]) << endl; // sum of contiguous subarray [l, r] (both inclusive)
    }

    return 0;
}

Answer 2

You can use segment tree which is usually for these kind of problems. Go through the link given below

https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/

Instead of the difference of two elements given(which is given in the link ) you can store the sum of the elements in the root. Hope it helps.