RMQ 세그먼트 트리의 버그

Question

RMQ를 수행하기위한 세그먼트 트리를 작성하려고합니다. 아무 래도 쿼리 범위에 관계없이 0을 반환합니다.

예를 들어, 내 배열은 [ 1,2,3,4,5,6,7,8,9,10 ]입니다. 인덱스 3에서 5 RMQ 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; 
} 

편집 : 모든 도움

감사합니다. 아래에 나온 대답과 마찬가지로 검색어 범위가 잘못되었습니다. 이 버그는이 구별도있다 :

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));

하고해야한다 트리를 수정하지 마십시오.

Answer 1

이 줄의 코드 :

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)); 

그리고 또한 당신의 업데이트 기능이 잘못되었습니다 :

Check Here