콘텐츠로 이동

제곱근 분할법

제곱근 분할법은 몇 가지 일반적인 연산(부분 배열 원소의 합 구하기, 최소/최대 원소 찾기 등)을 $O(\sqrt n)$번의 연산으로 수행할 수 있게 해 주는 방법(또는 자료 구조)이며, 이는 단순한 알고리즘의 $O(n)$보다 훨씬 빠릅니다.

먼저 이 아이디어의 가장 간단한 응용 중 하나를 위한 자료 구조를 설명하고, 이어서 이를 일반화하여 다른 문제들을 푸는 방법을 보인 다음, 마지막으로 이 아이디어를 약간 다르게 활용하는 방법인 입력 요청을 sqrt 블록으로 나누는 방법을 살펴봅니다.

제곱근 분할법 기반 자료 구조

배열 $a[0 \dots n-1]$이 주어질 때, 임의의 $l$과 $r$에 대해 원소 $a[l \dots r]$의 합을 $O(\sqrt n)$번의 연산으로 구할 수 있는 자료 구조를 구현하십시오.

설명

제곱근 분할법의 기본 아이디어는 전처리입니다. 배열 $a$를 길이가 약 $\sqrt n$인 블록들로 나누고, 각 블록 $i$에 대해 그 안의 원소 합 $b[i]$를 미리 계산해 둡니다.

블록의 크기와 블록의 개수가 모두 $\sqrt n$을 올림한 값과 같다고 가정할 수 있습니다:

$$ s = \lceil \sqrt n \rceil $$

그러면 배열 $a$는 다음과 같이 블록으로 나뉩니다:

$$ \underbrace{a[0], a[1], \dots, a[s-1]}_{\text{b[0]}}, \underbrace{a[s], \dots, a[2s-1]}_{\text{b[1]}}, \dots, \underbrace{a[(s-1) \cdot s], \dots, a[n-1]}_{\text{b[s-1]}} $$

마지막 블록은 다른 블록보다 원소가 적을 수 있지만($n$이 $s$의 배수가 아닌 경우), 이는 쉽게 처리할 수 있으므로 논의에서 중요하지 않습니다. 따라서 각 블록 $k$에 대해 그 안의 원소 합 $b[k]$를 알고 있습니다:

$$ b[k] = \sum\limits_{i=k\cdot s}^{\min {(n-1,(k+1)\cdot s - 1})} a[i] $$

이렇게 $b[k]$ 값을 계산했습니다(여기에는 $O(n)$번의 연산이 필요했습니다). 이 값들이 각 쿼리 $[l, r]$에 답하는 데 어떻게 도움이 될까요? 구간 $[l, r]$이 충분히 길면 여러 개의 온전한 블록을 포함하게 되며, 그러한 블록들에 대해서는 원소의 합을 한 번의 연산으로 구할 수 있다는 점에 주목하십시오. 결과적으로 구간 $[l, r]$에는 단 두 블록의 일부만 남게 되며, 이 부분들의 원소 합은 단순한 방법으로 계산해야 합니다.

따라서 구간 $[l, r]$의 원소 합을 계산하려면 두 "꼬리" $[l\dots (k + 1)\cdot s-1]$과 $[p\cdot s\dots r]$의 원소를 더하고, $k + 1$부터 $p-1$까지의 모든 블록의 $b[i]$ 값을 더하기만 하면 됩니다:

$$ \sum\limits_{i=l}^r a[i] = \sum\limits_{i=l}^{(k+1) \cdot s-1} a[i] + \sum\limits_{i=k+1}^{p-1} b[i] + \sum\limits_{i=p\cdot s}^r a[i] $$

참고: $k = p$일 때, 즉 $l$과 $r$이 같은 블록에 속할 때는 이 공식을 적용할 수 없으므로 합을 단순한 방법으로 계산해야 합니다.

이 방법을 사용하면 연산 횟수를 크게 줄일 수 있습니다. 실제로 각 "꼬리"의 크기는 블록 길이 $s$를 넘지 않으며, 합에 포함되는 블록의 개수도 $s$를 넘지 않습니다. $s \approx \sqrt n$으로 선택했으므로, 구간 $[l, r]$의 원소 합을 구하는 데 필요한 전체 연산 횟수는 $O(\sqrt n)$입니다.

구현

가장 간단한 구현부터 시작합시다:

// input data
int n;
vector<int> a (n);

// preprocessing
int len = (int) sqrt (n + .0) + 1; // size of the block and the number of blocks
vector<int> b (len);
for (int i=0; i<n; ++i)
    b[i / len] += a[i];

// answering the queries
for (;;) {
    int l, r;
  // read input data for the next query
    int sum = 0;
    for (int i=l; i<=r; )
        if (i % len == 0 && i + len - 1 <= r) {
            // if the whole block starting at i belongs to [l, r]
            sum += b[i / len];
            i += len;
        }
        else {
            sum += a[i];
            ++i;
        }
}

이 구현에는 나눗셈 연산이 지나치게 많습니다(나눗셈은 다른 산술 연산보다 훨씬 느립니다). 대신, 인덱스 $l$과 $r$을 포함하는 블록의 인덱스 $c_l$과 $c_r$을 계산하고, 블록 $c_l$과 $c_r$의 "꼬리" 부분은 따로 처리하면서 블록 $c_l+1 \dots c_r-1$을 루프로 순회할 수 있습니다. 이 방법은 설명의 마지막 공식에 해당하며, $c_l = c_r$인 경우를 특수한 경우로 만듭니다.

int sum = 0;
int c_l = l / len,   c_r = r / len;
if (c_l == c_r)
    for (int i=l; i<=r; ++i)
        sum += a[i];
else {
    for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)
        sum += a[i];
    for (int i=c_l+1; i<=c_r-1; ++i)
        sum += b[i];
    for (int i=c_r*len; i<=r; ++i)
        sum += a[i];
}

기타 문제

지금까지는 연속된 부분 배열의 원소 합을 구하는 문제를 다루었습니다. 이 문제는 개별 배열 원소를 갱신할 수 있도록 확장할 수 있습니다. 원소 $a[i]$가 바뀌면, 이 원소가 속한 블록($k = i / s$)의 $b[k]$ 값을 한 번의 연산으로 갱신하기만 하면 됩니다:

$$ b[k] += a_{new}[i] - a_{old}[i] $$

한편 원소의 합을 구하는 작업은 부분 배열의 최솟값/최댓값 원소를 찾는 작업으로 바꿀 수 있습니다. 이 문제에서도 개별 원소의 갱신을 처리해야 한다면 $b[k]$ 값을 갱신하는 것도 가능하지만, 블록 $k$의 모든 값을 순회해야 하므로 $O(s) = O(\sqrt{n})$번의 연산이 필요합니다.

제곱근 분할법은 다른 여러 부류의 문제에도 비슷한 방식으로 적용할 수 있습니다. 0인 원소의 개수 구하기, 0이 아닌 첫 번째 원소 찾기, 특정 성질을 만족하는 원소의 개수 세기 등이 그 예입니다.

또 다른 종류의 문제는 구간에 속한 배열 원소를 갱신해야 할 때 나타납니다. 기존 원소의 값을 증가시키거나 주어진 값으로 바꾸는 경우입니다.

예를 들어, 배열에 대해 두 가지 유형의 연산, 즉 구간 $[l, r]$의 모든 배열 원소에 주어진 값 $\delta$를 더하는 연산과 원소 $a[i]$의 값을 묻는 쿼리를 수행할 수 있다고 합시다. 블록 $k$의 모든 원소에 더해야 하는 값을 $b[k]$에 저장합시다(처음에는 모든 $b[k] = 0$입니다). 각 "더하기" 연산에서는 구간 $[l, r]$에 속하는 모든 블록에 대해 $b[k]$에 $\delta$를 더하고, 구간의 "꼬리"에 속하는 모든 원소에 대해 $a[i]$에 $\delta$를 더해야 합니다. 쿼리 $i$에 대한 답은 단순히 $a[i] + b[i/s]$입니다. 이렇게 하면 "add" 연산은 $O(\sqrt{n})$의 복잡도를 가지며, 쿼리에 답하는 것은 $O(1)$의 복잡도를 가집니다.

마지막으로, 작업에서 구간에 대한 원소 갱신과 구간에 대한 쿼리를 둘 다 수행해야 한다면 이 두 부류의 문제를 결합할 수 있습니다. 두 연산 모두 $O(\sqrt{n})$ 복잡도로 수행할 수 있습니다. 이를 위해서는 두 개의 블록 배열 $b$와 $c$가 필요합니다. 하나는 원소 갱신을 추적하고, 다른 하나는 쿼리에 대한 답을 추적합니다.

제곱근 분할법으로 풀 수 있는 다른 문제들도 있습니다. 예를 들어, 수를 추가/삭제하고, 어떤 수가 집합에 속하는지 확인하고, $k$번째로 큰 수를 찾을 수 있는 수의 집합을 유지하는 문제가 있습니다. 이를 풀려면 수를 오름차순으로 저장하되, 각각 $\sqrt{n}$개의 수를 담은 여러 블록으로 나누어야 합니다. 수가 추가/삭제될 때마다 인접한 블록의 시작과 끝 사이에서 수를 옮겨 블록들의 균형을 다시 맞춰야 합니다.

Mo 알고리즘

제곱근 분할법에 기반한 비슷한 아이디어를 사용하면 구간 쿼리($Q$)에 오프라인으로 $O((N+Q)\sqrt{N})$에 답할 수 있습니다. 이는 앞서 다룬 것보다 복잡도가 약간 나쁘고 두 쿼리 사이에 값을 갱신할 수도 없으므로, 이전 절의 방법들보다 훨씬 나빠 보일 수 있습니다. 하지만 많은 상황에서 이 방법은 장점이 있습니다. 일반적인 제곱근 분할법에서는 각 블록에 대한 답을 미리 계산해 두고, 쿼리에 답할 때 이를 병합해야 합니다. 어떤 문제에서는 이 병합 단계가 상당히 까다로울 수 있습니다. 예를 들어 각 쿼리가 해당 구간의 최빈값(가장 자주 나타나는 수)을 구하라고 요구하는 경우입니다. 이를 위해서는 각 블록이 블록 안의 각 수의 개수를 어떤 자료 구조에 저장해야 하며, 더 이상 병합 단계를 충분히 빠르게 수행할 수 없습니다. Mo 알고리즘은 완전히 다른 접근 방식을 사용하는데, 단 하나의 자료 구조만 관리하고 그 자료 구조에 대한 연산도 쉽고 빠른 것뿐이므로 이러한 종류의 쿼리에 빠르게 답할 수 있습니다.

아이디어는 인덱스에 기반한 특별한 순서로 쿼리에 답하는 것입니다. 먼저 왼쪽 인덱스가 블록 0에 있는 모든 쿼리에 답하고, 그다음 왼쪽 인덱스가 블록 1에 있는 모든 쿼리에 답하는 식으로 진행합니다. 또한 한 블록의 쿼리들도 특별한 순서, 즉 쿼리의 오른쪽 인덱스 기준으로 정렬된 순서로 답해야 합니다.

앞서 말했듯이 단 하나의 자료 구조를 사용합니다. 이 자료 구조는 구간에 대한 정보를 저장합니다. 처음에는 이 구간이 비어 있습니다. (특별한 순서에서) 다음 쿼리에 답하려 할 때는, 현재 구간의 양쪽에서 원소를 추가/제거하여 쿼리 구간이 될 때까지 구간을 단순히 확장하거나 축소합니다. 이렇게 하면 한 번에 원소 하나만 추가하거나 제거하면 되며, 이는 우리의 자료 구조에서 꽤 쉽게 수행할 수 있을 것입니다.

쿼리에 답하는 순서를 바꾸므로, 이는 쿼리에 오프라인 방식으로 답하는 것이 허용될 때만 가능합니다.

구현

Mo 알고리즘에서는 현재 유지하고 있는 구간에 인덱스를 추가하는 함수와 구간에서 인덱스를 제거하는 함수, 두 가지를 사용합니다.

void remove(idx);  // TODO: remove value at idx from data structure
void add(idx);     // TODO: add value at idx from data structure
int get_answer();  // TODO: extract the current answer of the data structure

int block_size;

struct Query {
    int l, r, idx;
    bool operator<(Query other) const
    {
        return make_pair(l / block_size, r) <
               make_pair(other.l / block_size, other.r);
    }
};

vector<int> mo_s_algorithm(vector<Query> queries) {
    vector<int> answers(queries.size());
    sort(queries.begin(), queries.end());

    // TODO: initialize data structure

    int cur_l = 0;
    int cur_r = -1;
    // invariant: data structure will always reflect the range [cur_l, cur_r]
    for (Query q : queries) {
        while (cur_l > q.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < q.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < q.l) {
            remove(cur_l);
            cur_l++;
        }
        while (cur_r > q.r) {
            remove(cur_r);
            cur_r--;
        }
        answers[q.idx] = get_answer();
    }
    return answers;
}

문제에 따라 다른 자료 구조를 사용하고, 그에 맞게 add/remove/get_answer 함수를 수정할 수 있습니다. 예를 들어 구간 합 쿼리를 구해야 한다면, 처음에 $0$인 단순한 정수 하나를 자료 구조로 사용합니다. add 함수는 해당 위치의 값을 더한 뒤 답 변수를 갱신하기만 하면 됩니다. 반면 remove 함수는 해당 위치의 값을 뺀 뒤 답 변수를 갱신합니다. 그리고 get_answer는 그 정수를 반환하기만 합니다.

최빈값 쿼리에 답하려면, 현재 구간에서 각 수가 몇 번 등장하는지 저장하는 이진 탐색 트리(예: map<int, int>) 하나와, 수들의 등장 횟수를 (예를 들어 횟수-수 쌍으로) 순서대로 유지하는 두 번째 이진 탐색 트리(예: set<pair<int, int>>)를 사용할 수 있습니다. add 메서드는 두 번째 BST에서 현재 수를 제거하고, 첫 번째 BST에서 횟수를 증가시킨 뒤, 그 수를 다시 두 번째 BST에 삽입합니다. remove도 같은 작업을 수행하며, 횟수를 감소시킨다는 점만 다릅니다. 그리고 get_answer는 두 번째 트리를 보고 최선의 값을 $O(1)$에 반환하기만 합니다.

복잡도

모든 쿼리를 정렬하는 데에는 $O(Q \log Q)$가 걸립니다.

다른 연산들은 어떻습니까? add와 remove는 몇 번 호출됩니까?

블록 크기를 $S$라고 합시다.

왼쪽 인덱스가 같은 블록에 있는 쿼리들만 보면, 이 쿼리들은 오른쪽 인덱스 기준으로 정렬되어 있습니다. 따라서 이 쿼리들 전체를 합쳐도 add(cur_r)와 remove(cur_r)는 $O(N)$번만 호출됩니다. 따라서 모든 블록을 합하면 $O(\frac{N}{S} N)$번의 호출이 발생합니다.

cur_l의 값은 두 쿼리 사이에서 최대 $O(S)$만큼 변할 수 있습니다. 따라서 add(cur_l)와 remove(cur_l)의 호출이 추가로 $O(S Q)$번 발생합니다.

$S \approx \sqrt{N}$이면 전체 연산 횟수는 $O((N + Q) \sqrt{N})$입니다. 따라서 복잡도는 $O((N+Q)F\sqrt{N})$이며, 여기서 $O(F)$는 add와 remove 함수의 복잡도입니다.

실행 시간 개선을 위한 팁

  • 블록 크기를 정확히 $\sqrt{N}$으로 잡는 것이 항상 최선의 실행 시간을 보장하지는 않습니다. 예를 들어 $\sqrt{N}=750$일 때 블록 크기를 $700$이나 $800$으로 잡는 편이 더 빠를 수도 있습니다. 더 중요한 점으로, 블록 크기를 실행 중에 계산하지 말고 const로 만드십시오. 상수로 나누는 연산은 컴파일러가 잘 최적화합니다.
  • 홀수 번째 블록에서는 오른쪽 인덱스를 오름차순으로, 짝수 번째 블록에서는 내림차순으로 정렬하십시오. 일반적인 정렬에서는 매 블록이 시작될 때마다 오른쪽 포인터가 끝에서 처음으로 되돌아가므로, 이렇게 하면 오른쪽 포인터의 이동이 최소화됩니다. 개선된 방식에서는 이러한 되돌림이 더 이상 필요하지 않습니다.
bool cmp(pair<int, int> p, pair<int, int> q) {
    if (p.first / BLOCK_SIZE != q.first / BLOCK_SIZE)
        return p < q;
    return (p.first / BLOCK_SIZE & 1) ? (p.second < q.second) : (p.second > q.second);
}

더욱 빠른 정렬 방법에 대해서는 여기에서 읽을 수 있습니다.

연습 문제