0

我正在使用此段树实现来查找范围内的最大元素：

int TREE[10000000]={0};
int arr[100000];
int RMQ(int ss, int se, int qs, int qe, int index)
{
if (qs <= ss && qe >= se)
    return TREE[index];
if (se < qs || ss > qe)
    return INT_MIN;
int mid=ss+(se-ss)/2;
return max(RMQ(ss, mid, qs, qe, 2*index+1),(mid+1, se, qs,qe, 2*index+2));
}

int constructTree(int ss,int se,int si)
{
if (ss == se)
{
    TREE[si] = arr[ss];
    return arr[ss];
}
int mid=ss+(se-ss)/2;
TREE[si]= max(constructTree(ss,mid,si*2+1),constructTree(mid+1, se,si*2+2));
return TREE[si];
}

主要是我在做这样的事情：

int N,M;
cin>>N>>M;
for(int i=0;i<N;i++){
    cin>>arr[i];
}
constructTree(0,N-1,0);
while(M--){
    int L,R;
    cin>>L>>R;
    cout<<RMQ(0,N-1,L-1,R-1,0)<<endl;
}

但它给出了错误的结果。就像输入 N=5 和 M=1 和数组是 [3,1,3,2,1] 查询 L=1,R=1 它给出 8。请帮助查找错误。

我找不到我的代码有什么问题:(

4

1 回答 1

0

这段代码最糟糕的地方就是你的名字。它们没有意义，请学会给你的实体起正确的名字。它将帮助您调试并减少引入错误的机会。您还应该改进缩进。

这些也将使人们更有可能在未来回答您的问题，因为他们将更容易理解您发布的代码。

int TREE[10000000]={0};
int arr[100000];

如果你的数组只能有100 000元素，那么你的段树就不需要保存10 000 000. 我很惊讶你的程序没有崩溃，差不多 40 MB。

如果您有n元素并且您不想担心检查超出范围的索引，您可以声明您的树的大小2^k >= 2*n-1在您的情况下，这将是2^18 = 262 144.

除此之外，这看起来是错误的：

if (qs <= ss && qe >= se)

应该是，如果我正确地理解了你的神秘符号：

if (qs >= ss && se <= qe)

下一个条件：

if (se < qs || ss > qe)

看起来正确。

于 2015-08-15T20:20:29.213 回答