配列の連続したすべての部分配列の合計を保存する方法は？

Question

私はn個の要素に配列を持っています（1 < = n < = 200000）。私は、この配列から形成できるすべての連続したサブ配列の合計を見つけると仮定しています。私はすべての合計を見つけるO（n^2）アルゴリズムを持っていますが、私の問題は、n（n + 1）/ 2の要素があるので、どのデータ構造にも格納できません。したがって、大きなスペースを必要とする10^10の要素があります。これは私が得ている出力です。

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

私はあまりにも多くのメモリを使用しているため、私のコードでそれを推測します。以下は私のコードです。

#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; 
} 

他の方法がありますか？ご案内ください。

Answer 1

セグメントツリーは、通常、この種の問題のために使用できます。あなたはルートの要素の和を格納することができます代わりに（リンクに記載されている）与えられた二つの要素の差の

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

下記リンクを介して移動します。 お手伝いをしてください。