RMQ(Range Minimum Query), 구간의 최솟값 구하기 알고리즘

1. 한 쿼리당 O(sqrt(n)), 선처리 O(n)

n개의 원소들을 sqrt(n)개의 원소를 갖는 그룹으로 나누어 최솟값을 미리 저장해두면 한 쿼리당 최대 3*sqrt(n)의 시간만으로 구간의 최솟값을 구할 수 있다.

arr[11]={7,5,4,3,2,6,8,11,9,1,10};  // 0-base임에 유의
// 11개짜리 배열을 3(=sqrt(11))개 씩 나누어 전처리 해주자
int r=(int)sqrt(n);
void init(){
  for(int i=0;i<n;i++){
    if(i%r==0) group[i/r]=arr[i];
    else group[i/r]=min(group[i/r],arr[i]);
  }  
}
int rmq(int a, int b){  // [a,b]구간의 rmq query
  int ans=INT_MAX;
  int aa=a/r;
  int bb=b/r;
  for(int i=a;i<r*aa;i++) ans=min(ans,arr[i]);
  for(int i=aa;i<bb;i++) ans=min(ans,group[i]);
  for(int i=r*bb;i<=b;i++) ans=min(ans,arr[i]);
  return ans;
}

쿼리 함수에서 3개의 반복문 복잡도가 모두 O(sqrt(n)) 이하이다.

2. 한 쿼리당 O(log(n)), 선처리 O(n*log(n))

1의 아이디어와 유사하다.(parse table을 활용하자!)

memo[i][j]: j부터 j+(1«i)-1의 원소들 중 가장 작은 값을 저장(즉, j부터 2^i개의 원소들 중 최소값)

이러한 행렬을 미리 저장해 둔다면 우리는 하나의 쿼리당 log(구간의 크기)의 복잡도로 최솟값을 찾을 수 있다.

const int SZ=100005;  // 배열 최대 크기
const int MXH=20; // 넉넉하게 잡았다. log(SZ)보다 적당히 크면 된다.
int arr[SZ];  // 쿼리를 시행할 data
int memo[MXH][SZ]; // memoization 배열
int n;
void init_memoization(){
  for(int i=0;i<n;i++) memo[0][i]=arr[i];
  for(int i=1;i<MXH;i++){
    for(int j=0;j<n;j++){
      if((j+(1<<(i-1)))>=n) continue;
      memo[i][j]=min(memo[i-1][j],memo[i-1][j+(1<<(i-1))]);
    }
  }
}
int rmq(int a, int b){  //[a,b]
  int ans=INT_MAX;
  for(int i=MXH;i>=0;i--){
    if((b-a+1)&&(1<<i)){
      ans=min(ans,memo[i][a]);
      a+=(1<<i);
    }
  }
  return ans;
}