Ошибка в дереве сегментов RMQ

Я пытаюсь построить дерево сегментов для выполнения RMQ. Так или иначе, независимо от того, какой диапазон я запрашиваю, он вернет мне 0.

Например, мой массив [ 1,2,3,4,5,6,7,8,9,10 ], RMQ от индекса 3 до 5 должен дать 4. Но мой код продолжает выводить 0.

Мой код:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll N, st[2*100000], arr[100000];

void build(int r, int lo,int hi) {
if(lo==hi) {
st[r] = arr[lo];
} else {
build(r<<1,lo,(lo+hi)>>1);
build((r<<1)|1,((lo+hi)>>1)+1,hi);
st[r] = min(st[r<<1],st[(r<<1)|1]);
}
}

void update(int r,int lo,int hi,ll val,int i) {
if(lo==hi) {
st[r] = val;
} else {
int mid = (lo+hi)>>1;
if(lo <= i && i <= mid) {
update(r<<1,lo,mid,val,i);
} else {
update((r<<1)|1,mid+1,hi,val,i);
}
st[r] = min(st[r<<1],st[(r<<1)|1]);
}
}

ll query(int r,int lo,int hi,int a,int b) {
if(lo > b || hi < a) {
return LLONG_MAX;
} else if(lo <= a && hi >= b) {
return st[r];
} else {
int mid = (lo+hi)>>1;
return st[r] = min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));
}
}

int main(void) {
for(int i = 0; i <= 10; i++) arr[i] = i;
build(1,0,10);
cout << query(1,0,10,3,5) << endl;
return 0;
}

Редактировать:

Спасибо за помощь. Как и в ответе ниже, мой диапазон запросов был неверным. Кроме этого есть 2 ошибки:

if(lo <= a && hi >= b) должно быть (a <= lo && b >= hi)

а также

return st[r] = min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

должно быть

return min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

так как я делаю только запросы и не должен модифицировать дерево.

0

Решение

Эта строка кода:

return st[r] = min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

почему ты меняешь a а также b Короче говоря, вы меняете свой запрос при каждом рекурсивном вызове.
так должно быть

 return st[r] = min(query(r<<1,lo,mid,a,b),query((r<<1)|1,mid+1,hi,a,b));

А также ваша функция обновления неверна:

Проверьте здесь

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]