C++ 构建分段树时出现分段错误

Question

我正在尝试构建一个段树来计算在数组给定间隔内具有最大总和的子数组......(对于每个查询(

我在函数"void build(("中遇到分段错误，我已经检查了数组大小....当尺寸较小时，这工作正常...但是对于较大的阵列大小，会发生分段错误。.

提前感谢：(

success test case:
3 
-1 2 3
1
1 2
2
seg fault test case:
90
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
324 3 23 -234 32 -4 324 435 -5775
9
1 4
3 5
5 9
1 40
2 50
5 90
10 40
50 90
30 50

<pre><code>
#include<iostream>
#include<limits.h>
#include<math.h>
using namespace std;
typedef struct node node;
struct node{
long int sum;
long int lbest;
long int rbest;
long int max;
};

void build(node *tree , long int n , long int start , long int end , long int *ar ){
if(start == end){
tree[n].sum = tree[n].lbest = tree[n].rbest = tree[n].max = ar[start];
return ;
}
else{
long int mid = (start + end)/2;
build(tree , (2*n) +1 , start , mid , ar);
build(tree , (2*n) +2 , mid+1 , end , ar);
tree[n].sum = tree[2*n+1].sum + tree[2*n+2].sum;
tree[n].lbest = max(tree[2*n+1].lbest , tree[2*n+1].sum + tree[2*n+2].lbest);
tree[n].rbest = max(tree[2*n+2].rbest , tree[2*n+2].sum + tree[2*n+1].rbest);
tree[n].max = max(tree[n].sum , max(tree[n].lbest , tree[n].rbest));
//     cout<<start<<" "<<end<<" -- "<<n<<" ";
//     cout<<" else "<<endl;
}
}
long int query(node *tree , long int  n , long int l , long int r , long int start , long int end){
if(l > end || r < start)return INT_MIN;
if(start >= l && end <= r)return tree[n].max;
long int mid = (start + end)/2;
return max(query(tree, (n*2)+1 , l , r , start , mid) , query(tree , 2*n+2 , l , r, mid +1 , end));
}


int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);

long int n , q;
scanf("%ld" , &n);
long int ar[n];
for(long int i = 0 ;i< n ; i++)cin>>ar[i];
long int nn = n*2;
node tree[nn+1];
build(tree, 0 ,0,n-1 ,ar);
scanf("%ld" , &q);
while(q--){
long a , b ;
scanf("%ld %ld" , &a ,&b);
a-- ;b--;
printf("%ldn" ,query(tree, 0 , a , b, 0 , n-1));
}

return 0;
}


</code></pre>

Answer 1

段树的最小大小必须为 2^(ceil(log(n((+1(-1，其中 n 是数组中的元素数。

---

只需将段树大小增加到 3*n 即可。

来源 ： https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/