쿼리 √N / √Q 버킷팅

Sqrt Query Bucket, 쿼리 버킷팅, Square Root Query Decomposition

정의

쿼리 √N / √Q 버킷팅 은 쿼리들을 √N 또는 √Q 개씩 묶어 일괄 처리해 원래 O(Q·log N) 또는 O(N·Q) 였던 비용을 O((N + Q)·√N) 등으로 줄이는 패턴.

Regions Trick 의 한 형태. 영역 = √N 개 쿼리 묶음 으로 보고 처리.

문제 상황과 동기

로그가 안 통하는 자료구조

세그먼트 트리나 펜윅 트리처럼 갱신·조회 모두 O(log N) 인 자료구조가 있으면 문제는 간단하다. 하지만 갱신은 log 로 되는데 삭제는 안 된다, 또는 조회는 빠른데 갱신이 너무 비싸다 (SCC 재계산, MST 재계산 등) 같은 자료구조를 다룰 때가 있다.

예를 들어 N 개 정점 그래프에 간선을 동적으로 추가하면서 “현재 x-y 가 같은 SCC 에 있나요?” 를 물을 때, 간선 하나 추가마다 전체 SCC 를 다시 구하면 O(Q·N). Q=10^5, N=10^5 면 10^10 으로 불가능.

Naive 접근: 매 쿼리 (갱신 또는 조회) 마다 O(N) 또는 O(N log N) 비용 재계산 → 전체 O(Q·N).

√Q 버킷팅의 돌파구: √Q 개의 갱신 쿼리마다 한 번만 자료구조를 완전 재구축하고, 그 사이 조회 쿼리는 이전 체크포인트 + 버퍼에 쌓인 최근 √Q 개 변경사항 을 함께 보며 답한다. 각 버킷 당 O(N) 재구축, 버킷 내 √Q 개 조회 각각 O(√Q) → 한 버킷 O(N + Q). 전체 O((Q/√Q)·N + Q) = O((N + Q)·√Q).

전형적 문제

• Offline incremental SCC / MST: 간선을 순서대로 추가만 하고, 중간중간 연결성 / SCC 질의. √Q 마다 스냅샷.
• Add / Query / Remove 비대칭: Add 는 O(1), Remove 는 O(N) 인 자료구조. √Q 개 Remove 를 모아 일괄 처리.
• 대량 업데이트 후 조회: 갱신이 몰려 있고 조회가 몰려 있을 때, 갱신 √Q 개 묶어 적용.

시각화

핵심 아이디어

쿼리가 온라인이라도 (점진적 갱신 / 점진적 조회), √N 개를 모은 뒤 처리하면 다음 이득.

1. 묶음 단위로 사전계산 으로 묶음 내 쿼리에 O(1) 또는 O(√N) 응답
2. 전체 갱신 / 조회 누적 으로 amortized 단순화
3. 세그먼트 트리 / 자료구조 갱신 을 √N 마다 한 번씩

핵심 불변량: 전체 상태 = 마지막 체크포인트 (checkpoint) + 현재 버퍼 (buffer). 조회 쿼리는 두 부분을 함께 보고 답한다. 갱신 쿼리는 버퍼에 쌓이다가 √Q 개 차면 체크포인트에 통합.

예제 추적

N=9 개 정점, Q=9 쿼리, √Q=3. 간선 추가와 “x-y 연결?” 질의를 섞어서 받는다.

초기: 정점 0-8, 간선 없음
checkpoint_graph = empty
buffer = []

Batch 1 (쿼리 0-2):
  0: add edge (0,1)     -> buffer.append((0,1))
  1: add edge (1,2)     -> buffer.append((1,2))
  2: query "0-2 연결?"  -> checkpoint + buffer 통합해 확인 → YES
  len(buffer)=2 < 3, 계속

Batch 2 (쿼리 3-5):
  3: add edge (3,4)     -> buffer.append((3,4)), len=3 → 체크포인트 통합
     checkpoint_graph := checkpoint + buffer 재구축 O(N)
     buffer 초기화
  4: add edge (4,5)     -> buffer.append((4,5))
  5: query "0-5 연결?"  -> checkpoint (0-2 연결) + buffer (3-5 연결) → NO

Batch 3 (쿼리 6-8):
  6: add edge (2,3)     -> buffer.append((2,3)), len=2
  7: query "0-5 연결?"  -> checkpoint + buffer 통합 → YES (0-1-2-3-4-5)
  8: add edge (6,7)     -> buffer.append((6,7)), len=3 → 통합
     checkpoint_graph := 전체 재구축
     buffer 초기화

총 재구축 횟수: 2회 (Batch 2 시작, Batch 3 끝)
각 재구축 O(N), 전체 O((Q/√Q)·N) = O(√Q·N)

응용 패턴

1. Add / Remove / Query 비대칭

Add 는 쉽지만 Remove 가 비싸면, Remove 만 모아서 √N 마다 일괄 처리. 그 사이 query 는 모인 Remove 를 제외한 상태 로 답변.

2. 그래프 간선 추가 + 연결성

간선 추가는 union-find 로 빠르지만 삭제는 어려움. √Q 개씩 묶고 해당 묶음에 영향받지 않는 쿼리 와 영향받는 쿼리 분리.

3. 쿼리에 대한 체크포인트 자료구조

매 √N 마다 전체 자료구조 스냅샷 → 그 사이 쿼리는 스냅샷 + 마지막 √N 개 갱신만 보면 됨.

4. Mo’s 와의 관계

Mo’s 가 입력 인덱스 (l, r) 의 √N 버킷팅이라면, 이건 쿼리 순서 의 √N 버킷팅. 직교적.

구현

다음은 간선 추가 + 연결성 질의를 √Q 마다 체크포인트 스냅샷으로 처리하는 골격.

// O(Q·sqrt(Q)·alpha(N)), O(N + Q) 메모리. log가 안 되는 자료구조를 sqrt(Q) amortized로
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool merge(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
        return true;
    }
    bool same(int a, int b) { return find(a) == find(b); }
};

int main() {
    int N, Q; cin >> N >> Q;
    int B = max(1, (int)sqrt(Q)); // 버킷 크기
    
    vector<pair<int,int>> checkpoint_edges; // 마지막 체크포인트의 간선들
    vector<pair<int,int>> buffer; // 현재 버퍼
    
    for (int i = 0; i < Q; i++) {
        string op; int u, v;
        cin >> op >> u >> v;
        
        if (op == "add") {
            buffer.push_back({u, v});
            // 버퍼 가득 차면 체크포인트 재구축
            if ((int)buffer.size() == B) {
                checkpoint_edges.insert(checkpoint_edges.end(), buffer.begin(), buffer.end());
                buffer.clear();
            }
        } else { // query
            // checkpoint + buffer 통합한 DSU 구축
            DSU ds(N);
            for (auto [a,b] : checkpoint_edges) ds.merge(a, b);
            for (auto [a,b] : buffer) ds.merge(a, b);
            cout << (ds.same(u, v) ? "YES" : "NO") << "\n";
        }
    }
}

구현 팁

1. 버킷 크기: B = sqrt(Q) 를 미리 계산. 너무 작으면 재구축 비용, 너무 크면 버퍼 조회 비용.
2. offline 으로 전환 가능하면: 쿼리 순서 바꿀 수 있다면 Mo’s Algorithm 이나 Offline Incremental SCC / MST 가 더 빠를 수 있음.
3. 메모리: 체크포인트 자료구조가 O(N) 이면 전체 O(N + Q). 버퍼는 최대 √Q 개.

복잡도 (일반)

작업	비용
한 batch (√N 쿼리) 처리	O(N + √N · (single query cost))
전체	O((N + Q) · √N) 또는 O((N + Q) · √Q)

Q ~ N 이면 √N 과 √Q 는 같은 차원.

함정

1. 단순 자료구조로 충분한지 검증

세그먼트 트리 / 펜윅 트리로 O(log N) 가 가능하면 그게 더 빠르다. 버킷팅은 log 가 안 되는 경우.

2. 답이 batch 의존적

batch 안에서 한 쿼리 결과가 다음 쿼리의 입력이 되는 interactive 케이스는 직접 적용 불가. interactive batching 변형.

3. 메모리

batch 마다 자료구조 복제하면 O(N · √Q). 신중한 reuse.

4. tie-break / 정렬

같은 위치 / 같은 시각의 batch 안 쿼리 순서를 명확히. 답이 흔들리지 않게.

BOJ 연습 문제

번호	제목	링크
BOJ 17635	다리	kokoa-lab
BOJ 5823	코끼리	kokoa-lab
BOJ 18254	쿼리와 쿼리	kokoa-lab
BOJ 16793	Collapse	kokoa-lab

참고

• Regions Trick
• Offline Incremental SCC / MST
• Segment Tree Beats
• Bulldozer Trick