c++ - 如何存储数组的每个连续子数组的总和？

Question

我有一个包含 n 个元素的数组 (1 <= n <= 200000)。我想找到可以从此数组形成的每个连续子数组的总和。我有一个 O(n^2) 算法可以找到所有和，但我的问题是我不能将它存储在任何数据结构中，因为有 n(n+1)/2 个元素。因此将有 10^10 个元素，这将需要很大的空间。这是我得到的输出。

在抛出“std::bad_alloc”实例后调用终止 什么():std::bad_alloc 中止(核心转储)

我猜是因为我的代码使用了太多内存。以下是我的代码。

#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/

您可以将元素的总和存储在根中，而不是给定的两个元素的差值(在链接中给出)。 希望对您有所帮助。