Offline Queries (오프라인 쿼리)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 4분 · 1,241자/단어 #algorithm #query #offline-queries #mo

정의

오프라인 쿼리 (Offline Queries) 는 쿼리가 주어진 순서대로 처리하지 않고, 효율성을 위해 재정렬하거나 배치 처리 하는 기법. 쿼리를 다시 정렬하여 정렬 상태를 유지하거나 포인터 이동을 최소화함으로써 전체 복잡도를 낮춘다.

대표적 기법: Mo’s algorithm (블록 단위 정렬), CDQ 분할 정복, 병렬 이분 탐색 (PBS), 오프라인 스위핑.

문제 상황과 동기

온라인 쿼리는 입력 순서대로 즉시 답해야 함. 반면 오프라인은 모든 쿼리를 미리 읽고 재정렬 가능.

naive (online): 각 쿼리마다 O(N) 처리. Q 개 쿼리면 O(NQ).
Mo’s algorithm: 쿼리를 (block(L), R) 기준 정렬. O((N + Q) sqrt(N)).
정렬 응용: 구간 합 쿼리를 L 기준 정렬하면 포인터 이동 O(N + Q).
스위핑: 이벤트를 x 좌표 기준 정렬하여 순차 처리.

핵심 통찰: 쿼리 순서를 바꿔도 최종 답변 집합은 동일. 포인터 이동 비용 최소화가 목표.

시각화

핵심 아이디어

Mo’s Algorithm (쿼리 제곱근 분할)

쿼리를 다음 기준으로 정렬:
  1. L / sqrt(N) (블록 번호) 오름차순
  2. 블록 내에서는 R 오름차순

포인터 curL, curR 을 이동하며 답 갱신:
  add(pos): 현재 구간에 a[pos] 추가
  remove(pos): 현재 구간에서 a[pos] 제거

총 이동 거리:
  L 포인터: Q * sqrt(N)
  R 포인터: N * sqrt(N)
  전체: O((N + Q) sqrt(N))

오프라인 스위핑

1. 이벤트 (쿼리, 갱신 등) 를 한 축으로 정렬
2. 정렬된 순서로 순회하며 자료구조 갱신
3. 각 쿼리 시점의 자료구조 상태로 답변

예: 구간 최댓값 쿼리 -> R 기준 정렬, 세그먼트 트리 유지

CDQ 분할 정복

1. 왼쪽 반을 처리
2. 왼쪽 -> 오른쪽 영향 전파
3. 오른쪽 반을 처리

시간 축을 분할 정복으로 오프라인 처리.

알고리즘

Mo's algorithm for range sum:
    B = int(sqrt(N))

    sort queries by (L / B, R if same block)

    curL = 0, curR = -1, curSum = 0
    for each (l, r, idx) in sorted queries:
        while curL > l: curL--; curSum += a[curL]
        while curR < r: curR++; curSum += a[curR]
        while curL < l: curSum -= a[curL]; curL++
        while curR > r: curSum -= a[curR]; curR--
        ans[idx] = curSum

구현

// Mo's algorithm: offline range sum queries
// 쿼리를 (block, R) 순서로 정렬해 O((N+Q)sqrt(N))
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q; cin >> n >> q;
  vector<int> a(n);
  for (auto& v : a) cin >> v;

  struct Query { int l, r, idx; };
  vector<Query> queries(q);
  for (int i = 0; i < q; i++) {
      cin >> queries[i].l >> queries[i].r;
      queries[i].l--; queries[i].r--;  // 0-indexed
      queries[i].idx = i;
  }

  int B = int(sqrt(n)) + 1;
  sort(queries.begin(), queries.end(),
      [B](const Query& x, const Query& y) {
          int bx = x.l / B, by = y.l / B;
          if (bx != by) return bx < by;
          return (bx & 1) ? (x.r > y.r) : (x.r < y.r);
      });

  vector<ll> ans(q);
  ll cur = 0;
  int L = 0, R = -1;
  for (auto& qq : queries) {
      while (L > qq.l) { L--; cur += a[L]; }
      while (R < qq.r) { R++; cur += a[R]; }
      while (L < qq.l) { cur -= a[L]; L++; }
      while (R > qq.r) { cur -= a[R]; R--; }
      ans[qq.idx] = cur;
  }

  for (ll v : ans) cout << v << "\n";
}

# Mo's algorithm for range sum queries
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
a = list(map(int, input().split()))

queries = []
for i in range(q):
  l, r = map(int, input().split())
  l -= 1; r -= 1  # 0-indexed inclusive
  queries.append((l, r, i))

B = int(n ** 0.5) + 1
queries.sort(key=lambda x: (x[0] // B, x[1] if (x[0] // B) % 2 == 0 else -x[1]))

ans = [0] * q
cur = 0
L, R = 0, -1

for l, r, idx in queries:
  while L > l:
      L -= 1
      cur += a[L]
  while R < r:
      R += 1
      cur += a[R]
  while L < l:
      cur -= a[L]
      L += 1
  while R > r:
      cur -= a[R]
      R -= 1
  ans[idx] = cur

print("\n".join(map(str, ans)))

// Mo's algorithm offline range sum, O((N+Q)sqrt(N))
import java.util.*;
import java.io.*;

public class Main {
  static class Query {
      int l, r, idx;
      Query(int l, int r, int idx) {
          this.l = l; this.r = r; this.idx = idx;
      }
  }

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int q = Integer.parseInt(st.nextToken());
      int[] a = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++)
          a[i] = Integer.parseInt(st.nextToken());

      Query[] qs = new Query[q];
      for (int i = 0; i < q; i++) {
          st = new StringTokenizer(br.readLine());
          int l = Integer.parseInt(st.nextToken()) - 1;
          int r = Integer.parseInt(st.nextToken()) - 1;
          qs[i] = new Query(l, r, i);
      }

      int B = (int)Math.sqrt(n) + 1;
      Arrays.sort(qs, (x, y) -> {
          int bx = x.l / B, by = y.l / B;
          if (bx != by) return bx - by;
          return (bx % 2 == 0) ? x.r - y.r : y.r - x.r;
      });

      long[] ans = new long[q];
      long cur = 0;
      int L = 0, R = -1;

      for (Query qq : qs) {
          while (L > qq.l) { L--; cur += a[L]; }
          while (R < qq.r) { R++; cur += a[R]; }
          while (L < qq.l) { cur -= a[L]; L++; }
          while (R > qq.r) { cur -= a[R]; R--; }
          ans[qq.idx] = cur;
      }

      StringBuilder sb = new StringBuilder();
      for (long v : ans) sb.append(v).append("\n");
      System.out.print(sb);
  }
}

stdin

결과

6
9
15

복잡도

항목	값
Mo’s algorithm	O((N + Q) sqrt(N)) 시간, O(N + Q) 공간
오프라인 스위핑	O(N log N + Q log N) (정렬 + BIT/세그트리)
CDQ 분할 정복	O(N log^2 N) (2D partial order)
병렬 이분 탐색 (PBS)	O((N + Q) log N log X)

오프라인 기법 분류

기법	적용 조건	복잡도
Mo’s	구간 쿼리, add/remove 쉬운 경우 (합, distinct, xor)	O((N+Q) sqrt N)
스위핑 + BIT	2D orthogonal range, 구간 최대/합	O((N+Q) log N)
CDQ	3D partial order, DP 최적화	O(N log^2 N)
PBS	결정 문제로 변환 가능, 단조성	O((N+Q) log N log X)
D&C Offline	갱신 + 쿼리 혼합	O((N+Q) log N)

Mo’s Algorithm 최적화

홀짝 최적화 (Odd-Even Optimization)

짝수 블록: R 오름차순
홀수 블록: R 내림차순

R 포인터가 블록 끝까지 갔다가 다시 돌아오는 비용 절약.
전체 R 이동 거리 약 2N sqrt(N) -> N sqrt(N) 으로 반감.

블록 크기 튜닝

기본: B = sqrt(N)
최적: B = N / sqrt(Q) (R 이동 최소화)

add/remove 연산

각 add/remove 가 O(1) 이어야 Mo’s 가 효율적. O(log N) 연산이면 전체 O((N+Q) sqrt(N) log N).

함정

1. 쿼리 순서 보존

오프라인 정렬 후에도 원래 순서대로 답을 출력해야 함. idx 필드로 결과 배열에 저장.

2. add/remove 비용 과소평가

Mo’s 는 add/remove 가 O(1) 일 때만 효율. 세그먼트 트리 연산이 필요하면 차라리 스위핑이 나음.

3. 구간 경계 인덱스

inclusive / exclusive 혼동 주의. 보통 [l, r] inclusive 로 맞추고 while 루프 일관성 유지.

4. 갱신이 있는 경우

Mo’s 는 갱신 없는 정적 배열 가정. 갱신 필요시 Mo’s with updates (3D Mo) 또는 PBS 사용.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 13547	수열과 쿼리 5	-	kokoa-lab
BOJ 2912	백설공주와 난쟁이	-	kokoa-lab
BOJ 8462	배열의 힘	-	kokoa-lab
BOJ 16139	인간-컴퓨터 상호작용	-	kokoa-lab

참고

이 글의 용어 (6개)

누적 합 (Prefix Sum)algorithm: 정의 누적 합 (Prefix Sum) 은 배열 에 대해 (또는 1-indexed ) 을 미리 계산해 두고, 임의 구간 합 을 O(1) 에 구하는 정형. 문제 풀이에서 "구간 N …
병렬 이분 탐색 (Parallel Binary Search)algorithm: 정의 병렬 이분 탐색 (Parallel Binary Search, PBS) 은 Q 개의 쿼리를 각각 독립적으로 이분탐색하지 않고, 모든 쿼리의 이분탐색을 라운드별로 동시에 진행하…
세그먼트 트리 (Segment Tree)algorithm: 정의 세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트…
제곱근 분할 (Sqrt Decomposition)algorithm: 정의 제곱근 분할 (Sqrt Decomposition) 은 크기 N 배열을 √N 개씩 블록으로 나누고, 각 블록을 전처리해 구간 연산을 O(√N) 에 처리하는 자료구조 기법. 문…
CDQ 분할 정복 (CDQ Divide and Conquer)algorithm: 정의 CDQ 분할 정복 은 오프라인에서 3차원 이상의 부분 순서 (partial order) 문제를 O(N log² N) 에 해결하는 기법. 한 축으로 분할하고, 다른 축을 2D…
Mo's Algorithm (Mo's)algorithm: 정의 Mo's Algorithm 은 오프라인 구간 쿼리를 (L, R) 정렬로 재배치해 포인터 이동을 amortized O((N+Q)√N) 으로 줄이는 기법. 문제 상황과 동기 크…

이 개념을 다룬 위키 페이지 (1)

wiki전처리 (Precomputation)