제곱근 구조 - 알고리즘카

제곱근 최적화는 여러 용도로 사용할 수 있으며, 특히 자료구조에서 유용합니다.

#배열에서의 제곱근 분할법

세그먼트 트리를 모른다고 가정하고 다음 문제를 살펴봅시다.

문제. 길이가 $n$인 배열 $a$가 주어집니다. 다음 두 유형 중 하나에 해당하는 $q$개의 쿼리에 답해야 합니다:

구간 $[l, r]$의 합을 구합니다.
구간 [l, r]의 모든 원소를 $x$만큼 증가시킵니다.

전체 배열을 $c \approx \sqrt{n}$개의 원소씩 블록으로 나누고, 각 블록의 합을 계산합시다. 블록들은 서로 겹치지 않으므로, 전체적으로 $O(n)$에 동작합니다.

// c это и количество блоков, и также их размер; оно должно быть чуть больше корня
const int maxn = 1e5, c = 330;
int a[maxn], b[c], add[c];

for (int i = 0; i < n; i++)
    b[i / c] += a[i];

또한 크기가 $\sqrt n$인 배열 add를 만들어 블록 단위 덧셈의 지연 연산에 사용하겠습니다. 즉, $i$번째 원소의 실제 값은 a[i] + add[i / c]와 같다고 간주합니다.

이제 첫 번째 유형의 쿼리에 쿼리당 $O(\sqrt n)$번의 연산으로 답할 수 있습니다:

쿼리 범위 안에 완전히 포함되는 모든 블록에 대해서는 이미 계산해 둔 합을 가져와 더하기만 하면 됩니다.
쿼리와 일부만 겹치는 블록(최대 두 개로, 오른쪽 블록과 왼쪽 블록입니다)에 대해서는 필요한 원소들을 순회하면서 하나씩 답에 더합니다.

이를 구현하는 방식은 여러 가지가 있지만, 저자는 다음과 같은 방식을 선호합니다.

int sum(int l, int r) {
    int res = 0;
    while (l <= r) {
        // если мы находимся в начале блока и он целиком в запросе
        if (l % c == 0 && l + c - 1 <= r) {
            res += b[l / c];
            l += c; // мы можем прыгнуть сразу на блок
        }
        else {
            res += a[l] + add[l / c];
            l += 1;
        }
    }
    return res;
}

갱신도 거의 같은 방식으로 작성합니다 — 구간에 완전히 포함되는 조각에 대해서는 add와 합을 갱신하고, 나머지에 대해서는 개별 원소를 갱신합니다:

void upd(int l, int r, int x) {
    while (l <= r) {
        if (l % c == 0 && l + c - 1 <= r) {
            b[l / c] += c * x;
            add[l / c] += x;
            l += c;
        }
        else {
            b[l / c] += x;
            a[l] += x;
            l++;
        }
    }
 }

두 연산 모두 $O(\sqrt n)$에 동작합니다. 필요한 ‘중앙’ 블록은 항상 $\sqrt n$개 이하이고, 경계 블록에 있는 원소는 모두 합해 $2 \sqrt n$개 이하이기 때문입니다.

#내부 구조

제곱근 분할법의 블록에는 부분 구간에 대한 어떤 함수의 값뿐만 아니라 매우 다양한 자료구조도 저장할 수 있습니다.

예를 들어, 각 블록 내부의 해시 테이블을 사용하면 “구간에서 $x$와 같은 원소의 개수” 형태의 쿼리에 답할 수 있고, 정렬된 배열을 사용하면 “구간에서 $x$보다 작은 수의 개수"나 “직사각형 위의 합” 형태의 문제를 풀 수 있습니다.

이러한 경우 실행 속도는 블록 크기에 매우 크게 좌우됩니다. 앞에서는 간단히 하기 위해 블록의 개수와 크기 모두에 같은 상수를 사용했지만, 실제로는 이 값들을 따로 조정해야 하는 경우가 많습니다.

이를 위해서는 ‘블록’ 부분과 ‘개별’ 부분의 점근적 복잡도보다는 오히려 실제 상대적인 실행 시간을 살펴보아야 합니다. 어떤 트립을 탐색하는 것이 벡터화가 잘 되는 배열의 선형 순회보다 결코 로그 배만큼 느린 것이 아니라는 점을 고려해야 하기 때문입니다. 같은 이유로 제곱근 휴리스틱에서는 제곱근이 로그보다 ‘작은’ 경우가 매우 흔합니다.

#이동하는 원소

문제. 길이가 $n$인 배열 $a$가 주어집니다. 다음 세 가지 유형 중 하나인 $q$개의 쿼리에 답해야 합니다.

원소 $x$를 위치 $k$에 삽입합니다(그 왼쪽에는 정확히 $k$개의 원소가 놓이게 됩니다).
위치 $k$의 원소를 삭제합니다.
구간 $[l, r]$에서 최솟값을 찾습니다.

여기서는 세그먼트 트리를 적용할 수 없는 것과 같은 이유로 앞의 접근법을 그대로 적용할 수 없습니다. 원소를 삽입하거나 삭제하면 오른쪽에 있는 모든 원소의 인덱스가 바뀌기 때문입니다. 여기서는 고정된 인덱스에 얽매이지 않는, 좀 더 유연한 구조에 원소를 저장해야 합니다.

모든 원소를 제곱근 크기의 블록으로 나누고, 각 블록마다 그 블록에 속한 모든 원소의 리스트(vector 또는 이와 비슷한 다른 컨테이너)와 함께 해당 블록의 최솟값을 저장합시다.

이제 원소 삽입 쿼리가 들어오면 모든 블록을 순회하며 해당 블록(그 블록 앞까지의 원소 수는 $k$개보다 적고, 그 블록까지 포함하면 이미 더 많아지는 블록)을 찾은 뒤, 블록 전체를 처음부터 그 크기만큼의 시간에 다시 구성하는 방식으로 그 블록에 원소를 삽입합니다.

삭제도 거의 같은 방식으로 합니다. 필요한 블록을 찾고, 그 안에서 필요한 원소를 찾아 삭제합니다. 최솟값은 완전히 포함되는 모든 블록의 최솟값을 취하고, 양쪽 경계 블록 두 개에서는 선형 순회로 접두사 또는 접미사의 최솟값을 구합니다.

경계 블록을 찾기 위해 이제는 경계를 단순히 어떤 상수로 나눌 수 없다는 점에 유의하십시오. 블록의 크기가 동적이므로, 어떤 블록의 시작 인덱스를 찾으려면 그 앞에 있는 모든 블록의 크기를 합해야 합니다.

vector< vector<int> > blocks;

// возвращает индекс блока и индекс элемента внутри блока
pair<int, int> find_block(int pos) {
    int idx = 0;
    while (blocks[idx].size() <= pos)
        pos -= blocks[idx++].size();
    return {idx, pos};
}

이런 형태의 풀이는 처음 얼마 동안만 잘 동작합니다. 그때는 각 연산이 $O(\sqrt n)$개 이하의 블록과 $O(\sqrt n)$개 이하의 개별 원소만 살펴보게 되지만, 시간이 지나면 블록이 너무 많아지거나 지나치게 큰 블록이 생길 수 있습니다. 이 문제를 해결하는 방법은 두 가지가 있습니다:

추가 또는 삭제 연산을 할 때마다 영향을 받은 블록을 확인하여, 그 크기가 $2 \cdot \sqrt n$보다 크면 둘로 나누고, 또한 그 블록과 이웃 블록의 크기 합이 $n$보다 작으면 하나로 합칩니다.
전역 연산 카운터를 두고, $\sqrt q$개의 쿼리마다 전체 구조를 그냥 다시 구축합니다(배열로 다시 옮겨 적은 뒤 같은 크기의 블록으로 새로 나눕니다).

첫 번째 경우에는 split과 merge에 잠재적으로 $O(\sqrt n)$번의 연산을 쓰지만 불변식이 보장되고, 두 번째 경우에는 정확히 $\sqrt n$에 구축 비용을 곱한 만큼이 듭니다.

두 번째 방법이 코드로 구현하기 더 쉽습니다(어차피 구조는 처음에 한 번 구축해야 하기 때문입니다). 주목할 점은, 머지가 처음부터 다시 구축하는 것보다 저렴한 경우처럼, 구조를 재구축하는 것이 균형 잡힌 상태로 유지하는 것만큼 이득이 되지 않는 상황도 있다는 것입니다.

좀 더 실제적인 문제의 예로는 IOI 2011 「Dancing Elephants」가 있습니다.