Range Minimum Query

Range minimum은 배열이 주어져 있을 때, 연속한 구간의 최솟값을 구하는 것을 의미한다. 최솟값을 여러 구간에 대해 반복적으로 구하는것이 Range Minimum Query, 줄여서 RMQ라 부른다. 다양한 방법이 존재하여 PS를 처음 접하는 사람들이 한번 보고 넘어가기 좋은 내용인거 같다.

 

다음과 같은 노테이션을 사용하겠다.

n : 배열의 길이

X[1~n] : 주어진 배열

q : 쿼리의 개수

xi, yi : i번째 쿼리, X[xi]~X[yi] 중 최소인 값

 

1. 단순한 방법

전처리 : 無

업데이트 : 無

query당 : O(n)

특이사항 : 초등학생도 짤 수 있음

 

그냥 전부 탐색해주는 방법. 매 번 (l-r)개의 숫자를 직접 확인해보며 최솟값을 찾아주는 방법이다. 구간의 길이에 따라 달라지지만 최악의 경우 O(nq)의 시간이 걸리게 된다.

아무것도 없어보이는 방법이지만 한편으로는 절대적인 방법이다. q가 1이거나 작은 상수일 경우 가장 권장 되는 방법이다. 괜히 segment tree를 짜서 시간을 소모할 필요없다.

장점이 하나 더 있는데 배열의 변화에 영향을 받지 않는다. 이제 RMQ를 하다보면 중간중간 배열의 값이 수정되는 경우가 있는데 이 방법은 전혀 영향을 받지 않는다.

#include <cstdio>

const int N=1000100;
const int INF=0x3c3c3c3c;
int x[N];

int main(void) {
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", x+i);
    for(int i=1; i<=m; i++) {
    	int l,r;
        scanf("%d%d", &l, &r);
        
        int ans=INF;
        for(int j=l; j<=r; j++) ans=min(ans, x[j]);
        printf("%d\n", ans);
    }
}

 

2. 전부 전처리

전처리 : O(n^2)

업데이트 : O(n^2)

query당 : O(1)

특이사항 : 중학생도 짤 수 있음

 

모든 부분구간에 대해 미리 최솟값을 계산해주는 방법이다. O(n^2)의 시간복잡도로 처리가 가능하다. n이 작을 경우 충분히 가용할 수 있는 방법이다. 값의 변화에 대해서는 유연하지 못해 다시 전처리 해주어야 한다. 값이 변하지만 않는다면 모든 쿼리에 대해 연산 없이 처리 할 수 있어 코드가 짧아진다.

#include <cstdio>

const int N=1010;
const int INF=0x3c3c3c3c;
int x[N];
int pr[N][N];

void make() {
    for(int i=1; i<=n; i++) {
    	pre[i][i]=x[i];
        for(int j=i+1; j<=n; j++) {
            pre[i][j]=min(pre[i][j-1], x[j]);
        }
    }
}

int main(void) {
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", x+i);
    make();
    
    for(int i=1; i<=m; i++) {
    	int l,r;
        scanf("%d%d", &l, &r);
        printf("%d\n", pre[l][r]);
    }
}

 

3. Prefix(Suffix) Min

전처리 : O(n)

업데이트 : O(n)

query당 : O(1)

특이사항 : l=1(r=n)인 경우의 최솟값 밖에 못 구함

 

보통 합을 구할때 더 많이 쓰는 방법인데 f(1, x)의 값들을 전부 저장해주는 방법이다.

합의 경우 f(x,y)=f(1,y)-f(1,x-1) 정도의 식이 성립해서 임의의 부분합을 빠르게 구해 줄 수 있어서 굉장히 자주 사용되는 방법이다. 최솟값의 경우 위 식이 성립하지 않아 아쉽게 모든 구간에 대해는 구할 수 없다. 하지만 경우에 따라 1부터 최솟값만 찾고 싶을 때가 있을 수도 있고 그 경우에 한해 유용하게 사용 된다. 실제 사용된 예시로 올해 2019 ACM-ICPC 인터넷 예선 문제 D에서 이 방법을 사용하면 segment tree보다 더 좋은 시간복잡도로 문제를 해결할 수 있다.

전처리는 앞에서부터 쭉 보면 되므로 O(n)의 시간이 걸린다. 주어진 쿼리에 대해 O(1)의 시간밖에 걸리지 않는다. 아쉬운 점이 있다면 값의 변화가 있을 경우 변경 해주는데 최대 O(n)의 시간이 걸린다.

 

4. Sqrt Decomposition

전처리 : O(n)

업데이트 : O(1)

query당 : O(sqrt(n))

특이사항 : 알고리즘 공부의 시작

 

굉장히 강력한 아이디어이다. root(n)개씩 묶어서 최솟값을 저장해놓는 것이다. query 당 O(sqrt(n))이라는 비교적 적은 시간이 걸리며 업데이트 또한 매우 빠른 시간에 가능하다. PS나 알고리즘을 공부할 때 처음에 나오는 내용이다. Segment Tree로 가기 위한 첫 스텝이다. 시그멘트 트리가 상위호완 느낌이므로 코드는 생략하겠다.

 

 

5. Segement Tree(★★★★★)

전처리 : O(n) 

업데이트 : O(log n)

query당 : O(log n)

특이사항 : 유명함

 

가장 잘 알려져 있다. 모든 구간에 대해 log n의 시간에 최솟값을 계산할 수 있으며 값의 변화에 대해 유연하게 대응가능하다. 여러 블로그에 많이 나와있으므로 내용은 생략하겠다.

예전에 짜놓고 매번 복사해서 쓰는데 좋은 코드인지는 모르겠다.

 

6. Lazy Propagation

전처리 : O(n)

업데이트 : O(log n)

query당 : O(log n)

특이사항 : 구간업데이트 가능

 

기본 틀은 Segment Tree를 사용하는데 기능 하나를 추가해준 것이다. 구간 업데이트라는 특정 케이스를 효율적으로 처리해줄 수 있다. 구간 업데이트란 "X[2]~X[6]의 값 전부 7증가" 등의 경우를 의미한다.

https://www.acmicpc.net/blog/view/26

 

7. Sparse Table

전처리 : O(n log n)

업데이트 : 불가능

query당 : O(1)

특이사항 : 업데이트 불가능

 

RMQ를 O(1)에 구할 수 있게 해주는 방법이다. 처음 보면 아마 감탄할 것이다. min(A U B)=min( min(A), min(B) )를 사용하기 때문에 최솟값에서만 사용할 수 있는 방법이다.

 

길이가 2^k인 모든 구간들의 최솟값을 전처리 해주면 된다. 각 구간을 계산할 때 앞 절반과 뒤 절반으로 나누어 각각의 최솟값을 재귀적으로 구해 비교해주면 되기 때문에 O(1)의 시간에 계산이 가능하다. 대충 n log n개의 구간에 대해 계산해야 하므로 전처리에 걸리는 전체 시간은 O(n log n)이다. 쿼리가 주어지면 길이가 2의 거듭제곱인 두 구간으로 덮을 수 있고 두 구간의 최솟값을 비교해주면 된다.

 

8. Sparse Table upgrade

전처리 : O(n)

업데이트 : 불가능

query당 : O(1)

특이사항 : 업데이트 불가능

 

사실 이 얘기를 하고 싶어 포스팅을 하였다. O(1)에 계산할 수 있는 방법을 찾았으나 아직 성에 덜 찬 심심한 사람들이 전처리 시간까지 줄이는 방법을 내보였다. 보통 Sparse Table선에서 다 정리가 되기 때문에 실용성은 떨어지지만 재미있는 알고리즘이다. 출처는 오래되서 까먹음.

 

일단 LCA로 우회하여 해결하게 된다. Lowest Common Ancestor의 약자로 트리에서 임의의 두 노드를 잡았을 때 두 노드를 모두 포함하는 서브트리의 root가 되는 노드들 중 가장 낮은 친구를 찾는 문제이다. 두 알고리즘이 굉장히 밀접한 관게로 LCA도 RMQ를 이용하여 해결할 수 있으며 RMQ도 LCA로 해결할 수 있다.

여기서는 기가막히게도 RMQ를 O(n)에 해결하기 위해 LCA를 이용하는데 LCA를 해결하기 위해 다시 RMQ를 이용한다.

 

목차

Step1) RMQ->LCA

Step2) LCA->Reduced RMQ

Step3) Solve Reduce RMQ

 

Step 1) RMQ->LCA

일단 RMQ문제를 LCA문제로 바꿔야 한다. 예를 들어 배열 {7, 1, 5, 3, 4}이 있으면 아래와 같은 트리를 구성해야 한다.

x좌표 순으로 보면 71534로 원래 배열과 같으며 낮은 숫자가 위로간다. 이렇게 구성하고 나면 7과 5사이의 최솟값을 구할때 7과 5의 LCA를 구해주면 된다. 엄밀히 state해보겠다.

Cartesian Tree
-Cartesian Tree가 만족해야 하는 조건
일단 기본 구성은 바이너리 트리에 다음 두조건을 만족
1) x가 y의 조상이라면 x<=y
2) y가 x의 왼쪽 자손이라면 배열에서 y가 x보다 먼저 등장, 오른쪽 자손이라면 x가 먼저 등장

-Cartesian Tree의 존재성
존재성은 가볍게 하나 만들어주면 된다. 전체 배열 중 최솟값 중 하나 r을 root로 잡고 r 기준 좌측과 우측
열로 각각 Cartesian Tree를 재귀적으로 구성한 뒤 root의 왼쪽과 오른쪽 노드로 만들어주면 된다. 이 방법
로 구성한 트리가 Cartesain Tree가 되는 것은 자명하다. 하지만 이와 같은 방법으로 Tree를 구성하면 최솟값을 탐색하는데 최대 O(n)의 시간이 걸리므로 최대 O(n^2)의 시간이 걸리게 된다. 조금 머리를 써서 양쪽 끝에서부터 최솟값을 탐색해줘도 O(n log n)의 시간이 걸리는데 우리의 최종 목표는 O(n)의 전처리이기 대문에 아직 부족하다.

-Cartesian Tree를 만드는 방법
앞에서부터 차례대로 Cartesian Tree를 구성해 나갈거다. X[1,i]로 트리를 구성한 상태에서 X[i+1] 값을 추가하는 것을 생각해보겠다. root에서부터 우측 노드로만 타고 쭉 내려가는 것을 수열(="오른팔")이 t_1, t_2, ... t_k이라 하겠다. T[i+1]이 해당 수열에서의 위치를 찾아 줄 수 있는데 만약 t_j <= T < t_j+1 이라 하면 t_j의 오른쪽 노드를 T[i+1]로 바꿔주고 기존의 노드를 T[i+1]의 왼쪽에 넣어주면 여전히 Cartesian Tree를 유지하는 것을 알 수 있다. T[i+1]<t_1인 경우 T[i+1]를 root로 만들어주면 되고 t_k < T[i+1]이라면 t_k의 우측 노드에 T[i+1]을 추가해주면 된다.
해당 방법의 시간 복잡도를 생각해볼텐데 T[i+1]이 추가 되고 나면 "오른팔"이 t_1, t_2, ... , t_j, T[i+1]이 될 것이다. 뒤에꺼는 다 없어지게 되니까 스택을 이용해서 "오른팔"을 관리해주면 전체 Cartesian Tree를 O(n)에 구성할 수 있게 된다.
※참고 해볼만한 문제. https://www.acmicpc.net/problem/15604

-LCA=RMQ
(i가 j보다 먼저 등잘할 때) i와 j의 LCA를 k라 하겠다. LCA이므로 i와 j는 각각 k의 양측 서브트리에 잇을 것이고 i-k-j순으로 배열에 등장할 것이다. 만약 해당 구간에 k보다 더 작은 값이 존재한다면 k보다 먼저 i와 j를 양측 서브트리로 나눌 것이고 k가 LCA가 될 수 없어진다. 다라서 해당 구간에서 k가 가장 작은 값이 될 것이고 LCA=RMQ가 성립한다.

이렇게 Cartesian Tree를 이용하면 RMQ문제를 LCA 문제로 바꾸어 줄 수 있는데 여기까지 O(n)의 처리시간이 걸린다.

 

Step2) LCA -> reduced RMQ

이제 다시 LCA 문제를 다시 RMQ문제로 바꿔줄 것이다. 기본 RMQ로 완전 똑같이 돌아가면 의미가 없을 거싱고 살짝 변형된 RMQ문제로 돌아가게 된다. 이번에는 Euler Tour를 이용할 것이다.

이름만 붙었지 사실 그냥 DFS이다. 왼쪽 노드를 먼저 방문하며 방문하는 모든 점을 기록할 것이다. 위의 예시에 대해 일반 DFS를 하면 다음과 같이 될 것이다.

 

             1->7->3->5->4

 

이 때 1에서 7을 갔다가 3으로 가기 전에 다시 1로 돌아가는데 이 돌아가는 점도 모두 기록해주면 된다. 깊이까지 묶어서 저장해주겠다. (깊이, 인덱스)이다.

 

             (0,1)->(1,7)->(0,1)->(1,3)->(2,5)->(1,3)->(2,4)->(1,3)->(0,1)

 

이렇게 저장해주고 나면 LCA를 RMQ를 통해 구할 수 있다. 7과 3의 LCA를 구해보겠다. 일단 기록된 수열에서 7과 3을 찾을 것이다. 여러개 있을텐데 아무거나 찾아도 상관없다. (인덱스가 같은 값이 있을 경우 서술이 귀찮아지므로 값들이 전부 다르다 가정하겠다. 방법은 차이없다.)

2번째에 (1,7)이 있고 6번째에(1,3)이 있다. 이제 RMQ(2,6)을 계산해주면 (0,1)이 되는데 여기서 1이 LCA가 된다. 일반적인 경우에 대해 살펴보겠다.

x에서 y로 가기 위해서는 무조건 LCA를 지나야 한다. 또한 LCA 위로는 벗어날 수 없다. LCA 밖으로 벗어나고 나면 더 이상 x와 y를 들릴 수 없기 때문이다. 구간에 LCA보다 높은 점은 포함할 수 없지만 LCA는 무조건 포함되므로 x와 y의 RMQ가 LCA가 되는 것이 설명 된다.

 

여기까지 전처리에 걸리는 시간은 단순 dfs이므로 O(n)이다. query가 들어왔을 때 해당 값의 위치는 맵핑 해놓으면 금방 찾을 수 있기 때문에 여전히 O(n)의 전처리와 쿼리 당 O(1)의 시간을 초과하지 않았다.

 

LCA를 RMQ문제로 바꾸어 주었는데 기존의 RMQ문제와 차이가 무엇일까? 바로 인접한 값들의 차이가 1이라는 것이다. ±1 RMQ라고도 부르는 것 같은데 기존의 RMQ문제에서 인접한 값들의 차이가 무조건 1이라는 강력한 조건이 붙었다.

 

Step3) Solve reduced RMQ

베이스는 Sparse Table이다. K=(log n)/2라 하겠다.

일단 n개의 수를 K개씩 묶어서 구간을 구성할 것이다. 이런 구간들을 K-구간이라 부르겠다.

각 K-구간의 최솟값을 구해줄 수 있다. t=n/K개의 K-구간의 나올텐데 이를 이용하여 Sparse Table을 구성해줄 것이다.

구성하는데 걸리는 시간은 O( (n/K) log(n/K)) < O(n/K logK)=O(n)이다.

여기까지 하면 연속한 K-구간들의 최솟값을 O(1)에 구할 수 있게 된다.

이제 특정 쿼리가 들어오면, 양 끝 점을 포함하는 K-구간을 제외하면 전처리 해놓은 Sparse Table을 이용하여 O(1)시간에 계산할 수 있게 된다.

 

여기까지만 하면 각각의 쿼리 당 O(log n)의 시간에 해결할 수 있게 된다. 양 끝에 조금은 일일히 확인해주고 사이는 Sparse Table을 이용해 O(1)시간에 계산하는 방식이다. 이제 양 끝 조금을 줄이는 방법만 찾으면 된다. 만약 양 끝 점이 다른 K-구간이라면 prefix/suffix min등을 이용하여도 O(1)시간에 해결 가능하지만 결국 같은 K-구간에 포함되는 경우를 처리해야되고 의미가 없다.

 

아직까지 사용하지 않은 조건이 있는데 인접한 값의 차이가 1 또는 -1이라는 것이다. 이 조건에 의해 각 K-구간이 가질 수 있는 형태가 (첫번째 값을 기준으로) 2^K개 밖에 없다. 여기서 K는 굉장히 작은 값인데 무려 2^K을 해줘도 root(n)밖에 되지않는다. root(n)개의 모든 형태에 대해 K^2개의 모든 부분구간의 최솟값을 계산해주는데는 O(root(n) * K^2)=O(n)이면 충분하다.

각 K-구간이 어떤 형태인지 알아내는 것 또한 각각 O(k)의 시간이면 충분할 것이고 전체는 O(n)시간에 가능하다. 따라서 임의의 K-구간에 포함된 작은 구간들의 최솟값은 O(n)의 전처리만 해주면 O(1)시간에 구할 수 있게 된다.

 

끝났다. 지금까지의 내용을 합쳐주면 O(n)의 전처리만으로 각 쿼리의 최솟값을 O(1)시간에 찾아줄 수 있다.

배열이 주어지면 해당 배열로 Cartesian Tree를 구성하고, Eulor Tour를 통해 새로운 배열을 만들어주고 ±1 RMQ를 위한 전처리를 해놓으면 된다.

쿼리가 들어오게 되면 해당 쿼리의 Cartesian Tree에서의 위치를 찾고 두 점의 LCA를 ±1 RMQ를 통해 O(1)시간에 구해주면 된다. 코드는 의미없을 것 같으므로 생략 하겠다.