如何使用大數組大小？

我試圖在spoj上遇到這個問題。 www.spoj.com/problems/RRANGE.It需要段樹。但問題是與陣列的大小。這裏（1 < = N < = 1,000,000,000）。解決這個問題的任何方法？這是我實現（給出正確的答案几乎ñ< 1000000）如何使用大數組大小？

#include <stdio.h> 
#include <math.h> 
#include<iostream> 
#include<string.h> 
using namespace std; 
//segment tree 
long long a[1000000]; 

long long Mid(long long s,long long e) 
{ 
    return s+(e-s)/2; 
} 
long long Sum1(long long *st,long long ss,long long se,long long qs,long long qe,long long index) 
{ 
    if (qs<=ss&&qe>=se) 
     return st[index]; 
    if (se<qs||ss>qe) 
     return 0; 
    long long mid=Mid(ss, se); 
    return Sum1(st,ss,mid,qs,qe,2*index+1) +Sum1(st,mid+1,se,qs,qe,2*index+2); 
} 
void update1(long long *st,long long ss,long long se,long long i,long long diff,long long index) 
{ 
    if (i<ss||i>se) 
     return; 
    st[index]=st[index]+diff; 
    if (se!=ss) 
    { 
     long long mid = Mid(ss,se); 
     update1(st,ss,mid,i,diff,2*index+1); 
     update1(st,mid+1,se,i,diff,2*index+2); 
    } 
} 
void update(long long arr[],long long *st,long long n,long long i,long long new_val) 
{ 
    if (i<0||i>n-1) 
    return; 
    long long diff = new_val - arr[i]; 
    arr[i] = new_val; 
    update1(st,0,n-1,i,diff,0); 
} 
long long Sum(long long *st,long long n,long long qs,long long qe) 
{ 
    if (qs<0||qe>n-1||qs>qe) 
    return -1; 
    return Sum1(st,0,n-1,qs,qe,0); 
} 

long long segtree(long long arr[],long long ss,long long se,long long *st,long long si) 
{ 

    if (ss==se) 
    { 
     st[si]=arr[ss]; 
     return arr[ss]; 
    } 


    long long mid=Mid(ss, se); 
    st[si]=segtree(arr,ss,mid,st,si*2+1)+segtree(arr,mid+1,se,st,si*2+2); 
    return st[si]; 
} 

long long *segt(long long arr[],long long n) 
{ 
    long long x = (long long)(ceil(log2(n))); 
    long long max_size = 2*(long long)pow(2, x) - 1; 
    long long *st = new long long[max_size]; 
    segtree(arr,0,n-1,st,0); 
    return st; 
} 
int main() 
{ 
    //memset(a,0,sizeof(a)); 
    long long n,u,v; 
    cin>>n>>u>>v; 
    for(long long i=0;i<n;i++) 
    a[i]=0; 
    long long *st=segt(a,n); 


    while(u--) 
    { 
     long long i,j; 
     cin>>i>>j; 
     long long z=1; 
     for(long long p=i-1;p<j;p++) 
     { 
     update(a,st,n,p,a[p]+z); 
     z++; 
     } 
    //for(int m=0;m<n;m++) 
    //cout<<a[m]<<endl; 

    } 
    while(v--) 
    { 
     long long i,j; 
     cin>>i>>j; 
     cout<<Sum(st,n,i-1,j-1)<<endl; 
    } 
    return 0; 
}

來源

2013-12-17 techriften

那麼，非常大的N的具體問題是什麼？ – BoBTFish

對於我的意見問題沒有很好的制定。如果在編譯時你不知道數組中元素的確切大小，那麼有這樣的工具：std :: vector - 任何類型的變量大小的對象的容器。使用它更安全，並鼓勵每個人使用這個標準的便攜式工具來管理陣列。 –

在C或C++本地對象一般或通常被分配在堆棧中。因爲你正在堆棧上分配一個非常大的數組。所以你有機會獲得堆棧溢出。我建議你使用std::vector<int>並將其大小調整爲1000000個元素。

來源

2013-12-17 17:20:59

或者如果單個緩衝區的元素數量很大，則使用deque。 – 111111

+1堆棧溢出 –

或啓用分段堆棧？ –

無論您嘗試使用哪種解決方案，都需要超過8 GB的內存來解決使用此算法的問題。內存限制是很少的。想想一個需要更少內存的替代解決方案。

來源

2013-12-17 17:25:39

您可以嘗試使用binary indexed tree而不是segment tree - >here是一個nive教程。

與段樹的O（2 ^（logN + 2））相比，BIT佔用O（n）內存，並且它可以用於相同的目的。

希望這有助於...

來源

2013-12-17 17:46:12 Pandrei

如何使用大數組大小？

回答

相關問題