Поиск максимума с использованием дерева сегментов дает неверные результаты

У меня есть эта реализация дерева сегментов, чтобы найти максимальный элемент в диапазоне:

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. Пожалуйста, помогите найти ошибку.

Я не могу найти, что не так с моим кодом :(


c++ algorithm segment-tree
person mat7    schedule 15.08.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Самое худшее в этом коде - это ваши имена. Они не имеют смысла, пожалуйста, научитесь давать имена своим сущностям. Это поможет вам отладить, а также уменьшит вероятность появления ошибок. Вы также должны улучшить свой отступ.

Это также повысит вероятность того, что люди ответят на ваши вопросы в будущем, потому что им будет легче понять код, который вы публикуете.

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

Если ваш массив может содержать только 100 000 элементов, нет необходимости, чтобы дерево сегментов содержало 10 000 000. Я удивлен, что ваша программа не падает, это почти 40 МБ.

Если у вас есть 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)

Выглядит правильно.

person IVlad    schedule 15.08.2015