Regions Trick

Regions Trick, 쿼리 캐싱

정의

Regions Trick 은 비슷한 쿼리들을 시공간 영역으로 묶어 캐싱 해, 동일/유사 결과를 재사용해 총 비용을 줄이는 패턴. 쿼리 캐싱 (query caching) 의 다양한 변형 중 가장 일반적인 이름.

핵심: 한 쿼리당 O(F) 의 계산이 들 때, 비슷한 쿼리 (같은 영역 / 같은 시점 / 같은 인덱스 구간) 들을 한 번에 묶어 O(F + Q) 로. Mo’s algorithm 도 같은 정신.

문제 상황과 동기

오프라인 구간 쿼리 문제에서 각 [l, r] 쿼리를 독립적으로 처리하면 한 쿼리당 O(N) 으로 전체 O(QN). Q=10⁵, N=10⁵ 이면 10¹⁰ 으로 불가능.

Naive 접근

각 쿼리 [l, r] 마다 배열을 순회해 답 계산. 총 O(QN).

Regions Trick 의 돌파구

쿼리들이 비슷한 영역에 모여 있으면 한 번 계산하고 캐싱. Mo’s algorithm 이 대표적 instance: 쿼리를 √N 버킷으로 정렬한 뒤 슬라이딩 윈도로 이동하면 전체 이동 거리가 amortized O((N+Q) √N).

다른 예: 2D 쿼리 (x, y) 를 x 축으로 정렬 + y 축은 segment tree 로 관리 → 각 쿼리 O(log N).

어디서 쓰이나: 비슷한 [l, r] 구간들이 여러 번 등장하는 오프라인 문제, 시공간 평면의 직사각형 쿼리들, 트리 쿼리 묶음 등. 쿼리들이 비슷한 영역에 모여 있으면 한 번 계산하고 캐싱. Mo’s 가 대표 instance, amortized O((N+Q) √N).

시각화

핵심 아이디어

쿼리들이 시공간 평면 위 점이라 볼 때, 근접한 쿼리들은 답 변화가 작다. 영역으로 묶어 한 번 계산 → 영역 내 쿼리에 대해 O(1) 응답.

1. 모든 쿼리 수집 (오프라인 전제)
2. (i, j) 같은 인덱스 / (l, r) 같은 구간 / (t, x) 같은 시공간 좌표를 영역으로 분할
3. 영역 단위로 한 번 계산
4. 영역 안 쿼리에 cached 응답

영역의 정의가 문제마다 다르다. 직사각형 / 삼각형 / 정렬된 구간 다양.

Mo’s Algorithm 세부 단계

Mo’s 는 Regions Trick 의 가장 유명한 instance. 쿼리 [l, r] 들을 슬라이딩 윈도로 처리.

불변량: 현재 윈도 [L, R] (inclusive) 의 상태를 유지. add(x), remove(x) 함수로 윈도를 확장/축소.

정렬 규칙: 쿼리를 다음 키로 정렬:

1. l / BLOCK (블록 번호, BLOCK = √N)
2. 같은 블록 내에서는 r (짝수 블록은 오름차순, 홀수 블록은 내림차순)

이동 전략: 정렬 순으로 쿼리를 순회하며 L, R 을 이동. 각 블록 내에서 L 은 최대 √N 이동, R 은 단조 이동 → 전체 O((N+Q) √N).

예제 추적 (N=9, Q=3, BLOCK=3):

쿼리: [1,5], [2,7], [4,9]
정렬 후 (블록, r):
  [1,5] -> 블록 0, r=5
  [2,7] -> 블록 0, r=7
  [4,9] -> 블록 1, r=9

초기 L=1, R=0 (빈 윈도)

쿼리 [1,5]:
  L=1 (변화 없음), R=0 -> 5: add(1), add(2), ..., add(5)
  ans[0] = (현재 상태 조회)

쿼리 [2,7]:
  L=1 -> 2: remove(1)
  R=5 -> 7: add(6), add(7)
  ans[1] = (현재 상태 조회)

쿼리 [4,9]:
  L=2 -> 4: remove(2), remove(3)
  R=7 -> 9: add(8), add(9)
  ans[2] = (현재 상태 조회)

총 이동: L 이동 4회, R 이동 9회 -> O(Q √N)

구현

Mo’s algorithm 의 핵심 구조. add(x), remove(x) 는 문제에 따라 직접 구현.

// O((N+Q) √N), O(N+Q) 메모리 (Mo's 알고리즘 템플릿)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int BLOCK; // √N

struct Query {
    int l, r, idx; // [l, r] 구간 (inclusive), 쿼리 인덱스
};

int a[MAXN]; // 배열
int cnt[MAXN]; // 빈도 카운트 등 상태
int current_answer = 0; // 현재 윈도의 답

// 원소 x 를 윈도에 추가 (문제 의존적)
void add(int x) {
    // 예: 빈도 카운트
    if (cnt[a[x]] == 0) current_answer++;
    cnt[a[x]]++;
}

// 원소 x 를 윈도에서 제거 (문제 의존적)
void remove(int x) {
    cnt[a[x]]--;
    if (cnt[a[x]] == 0) current_answer--;
}

// Mo's 정렬: l 을 블록으로 나누고, 같은 블록 내에서는 r 정렬 (even/odd 블록은 반대)
bool mo_cmp(const Query& a, const Query& b) {
    int block_a = a.l / BLOCK;
    int block_b = b.l / BLOCK;
    if (block_a != block_b) return block_a < block_b;
    // 짝수 블록: r 오름차순, 홀수 블록: r 내림차순 (최적화)
    return (block_a & 1) ? (a.r > b.r) : (a.r < b.r);
}

int main() {
    int N, Q;
    cin >> N >> Q;
    BLOCK = sqrt(N);

    for (int i = 1; i <= N; i++) cin >> a[i];

    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }

    sort(queries.begin(), queries.end(), mo_cmp);

    vector<int> ans(Q);
    int L = 1, R = 0; // 현재 윈도 [L, R] (inclusive)

    for (auto& q : queries) {
        // [L, R] -> [q.l, q.r] 로 윈도 이동
        while (R < q.r) add(++R);
        while (L > q.l) add(--L);
        while (R > q.r) remove(R--);
        while (L < q.l) remove(L++);

        ans[q.idx] = current_answer;
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }
}

구현 팁

1. 블록 크기: BLOCK = sqrt(N) 이 이론적 최적. 실전에서는 300-700 사이 실험.
2. even/odd 최적화: 짝수 블록 r 오름차순, 홀수 블록 r 내림차순으로 R 의 지그재그 이동 줄임.
3. L, R inclusive: 윈도 [L, R] 은 양쪽 포함. ++R 전에 add(R+1) 아니라 add(++R) 주의.

변형들

1. Mo’s Algorithm

쿼리 (l, r) 들을 √N 버킷으로 정렬 → 슬라이딩 윈도로 답 갱신. 한 쿼리당 amortized O(√N).

2. Offline 2D Queries

(x, y) 평면 위 쿼리를 x 정렬 + segment tree on y 로 처리.

3. Persistent Segment Tree

각 시점 을 persistent 로 캐싱. 시점 t 의 상태 를 O(log N) 에 조회.

4. Sqrt 버킷팅

쿼리들을 √Q 개씩 묶어 한 번에 처리. Sqrt Query Bucket 참고.

응용 패턴

• 문자열 / 패턴 매칭에서 비슷한 위치 쿼리들
• 그래프에서 비슷한 시각 쿼리들
• 격자 / 평면에서 비슷한 영역 쿼리들
• 트리 DP 에서 비슷한 서브트리 쿼리들

복잡도

패턴	한 쿼리 비용
단순	O(F)
Mo’s algorithm	O(√N) amortized
영역 캐싱	O(F / 영역수 + 1) amortized
Persistent	O(log N)

함정

1. 오프라인 가정 필수

모든 쿼리를 미리 알아야 영역으로 분할 가능. 온라인이면 다른 방법.

2. 영역의 정의

문제마다 적절한 영역 크기 / 분할 방식 이 다르다. 너무 크면 단일 영역 계산이 비싸고, 너무 작으면 영역 수가 많아 cache miss 누적.

3. 답 갱신의 비대칭

영역을 add 하기 쉬워도 remove 가 어려우면 Mo’s 가 안 통할 수 있다. roll-back Mo’s 또는 분할정복 변형.

4. 정렬 비용

쿼리 정렬에 O(Q log Q). 영역 분할 정확도와 정렬 비용의 trade-off.

BOJ 연습 문제

번호	제목	링크
BOJ 12857	홍준이는 문자열을 좋아해	kokoa-lab
BOJ 1762	평면그래프와 삼각형	kokoa-lab
BOJ 25952	Rectangles	kokoa-lab
BOJ 22316	Regions	kokoa-lab
BOJ 25504	최적 경로와 쿼리	kokoa-lab
BOJ 25505	공통 부분 문자열 쿼리	kokoa-lab

참고

• Sqrt Query Bucket
• Bulldozer Trick
• Segment Tree Beats