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

Question

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

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

你可以使用通常用于此类问题的线段树。通过下面给出的link

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

您可以将元素的总和存储在根中，而不是给定的两个元素的差（在 link 中给出）。希望对你有帮助。

Answer 2

您正在 'std::bad_alloc' 因为您正试图分配如此多的静态内存。分配静态内存有一个限制，这取决于环境：OS 你在什么地方运行？那是 16 位、32 位、64 位内存架构吗？ .

替代方式

另一种方法将花费 O(n) 时间和 O(n) 辅助 space。您不需要计算每个连续子数组的总和。相反，计算总和并将其存储到新数组中的初始数组中的第 i 个元素。

如果初始数组 (A) 为 [5, 3, 9, 15, 21]，则新数组 (B) 将为 [5, 8, 17, 32, 53]。

每当你需要连续子数组 [l, r]（包括两者）的总和时，其中 l 是左索引（或起始索引），r 是右索引（或结束索引），你可以在 O(1) 时间内得到它，并且该总和将等于 B[r] - B[l] + A[l].

下面是相同的实现。

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

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

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

c++

arrays

algorithm

sub-array

替代方式