배열의 모든 인접한 부분 배열의 합계를 저장하는 방법은 무엇입니까?

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/

아래에 주어진. 도움이 되길 바랍니다.