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.