Bug dans l'arborescence du segment RMQ

Question

J'essaie de créer un arbre de segment pour effectuer RMQ. D'une manière ou d'une autre, quelle que soit la portée que j'interroge, elle me renvoie 0.

Par exemple, ma matrice est [ 1,2,3,4,5,6,7,8,9,10 ]. RMQ de l'indice 3 à 5 devrait donner 4. Mais mon code ne cesse de produire 0.

Mon code:

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

Edit:

Merci pour toute l'aide. Comme ce que la réponse ci-dessous mentionné, ma plage de requête était erronée. Il y a aussi 2 bugs En dehors de cela:

if(lo <= a && hi >= b) devrait être (a <= lo && b >= hi)

et

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

devrait être

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

depuis que je ne fais que fais des requêtes et devrait ne pas être en train de modifier l'arbre.

Answer 1

Cette ligne de code:

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

pourquoi vous changez votre a et b bref vous changez votre requête dans tous les appels récursifs. il devrait être

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

Et aussi votre fonction de mise à jour est erroné:

Check Here