寻找最大使用段树给出错误的结果

Question

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

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

在main中，我做了这样的事情:

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。请帮忙查找bug

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

Answer 1

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

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

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

如果你的数组只能包含100 000个元素，那么你的段树就不需要包含10 000 000。我很惊讶你的程序没有崩溃，那几乎有40mb了。

如果你有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)

看起来正确。