Sqrt Decomposition – 블럭으로 나누면 쿼리가 빨라진다

Sqrt Decomposition – 블럭으로 나누면 쿼리가 빨라진다

---

“쿼리 수는 많은데, 세그먼트 트리 쓰기엔 과하다고 느낀 적 있나요?”

이런 상황에서 정말 유용한 게 바로 Sqrt Decomposition,
한국말로는 제곱근 분할 기법입니다.

단순하면서도 강력한 쿼리 최적화 알고리즘으로,
초보자도 이해하기 쉽고 구현도 간단한 구조예요.

---

🎯 언제 쓰는가?

• 배열 길이: N ≤ 1e5
• 쿼리 수: Q ≤ 1e5
• 요구 연산이 너무 복잡하지 않을 때
• 예: 구간 합, 최댓값, 특정 값의 개수, 구간 곱 등

---

🧠 핵심 아이디어

배열을 √N 크기의 블럭으로 나눈다.
각 블럭에 대한 요약 정보를 미리 저장해둔다.
질의할 땐:

• 전체 블럭이면 O(1)
• 부분 블럭이면 O(√N) 이내

→ 결국 전체 쿼리는 O(√N × Q) 정도로 처리됨

---

📌 구조 설계

반응형

• arr: 원본 배열
• block: 블럭별 요약 정보 (합, 최대, 개수 등)
• block_size: int(sqrt(N))

import math

n = len(arr)
block_size = int(math.sqrt(n))
block = [0] * (block_size + 1)

# 초기화
for i in range(n):
    block[i // block_size] += arr[i]

---

✅ 구간 합 질의 예시

def query(l, r):
    sum_ = 0
    while l <= r and l % block_size != 0:
        sum_ += arr[l]
        l += 1
    while l + block_size - 1 <= r:
        sum_ += block[l // block_size]
        l += block_size
    while l <= r:
        sum_ += arr[l]
        l += 1
    return sum_

---

✍️ 값 업데이트 처리

def update(idx, val):
    block_idx = idx // block_size
    block[block_idx] += val - arr[idx]
    arr[idx] = val

업데이트까지 고려하면 정적 쿼리뿐만 아니라
동적 쿼리도 어느 정도 대응 가능합니다.

---

🧪 예제 문제 (BOJ)

• BOJ 1395 – 스위치
• BOJ 10836 – 식물
• BOJ 10090 – Inversion Counting → Binary Indexed Tree + sqrt

---

🔁 Sqrt 기법 확장 아이디어

유형 설명

Sqrt + HashMap	각 블럭에 defaultdict(dict) 저장 – 구간 내 개수 카운트
Sqrt + Lazy	블럭 전체에 동일한 연산을 할 때 Lazy Tag 사용
Sqrt + Mo	쿼리가 많고 블럭 이동이 많을 때 Mo와 병행 가능
Sqrt + Bit	각 블럭을 비트셋처럼 구성하면 공간 최적화

---

🏁 정리

• 블럭 단위로 처리하면 훨씬 빠른 시간에 구간 쿼리를 처리 가능
• 세그먼트 트리에 비해 구현 난이도 ↓, 속도도 실용적
• Sqrt 기법은 어디에든 응용 가능 (트리, 2D 배열, 문자열 등)

👉 다음 글에서는
오프라인 쿼리 + 유니온파인드를 조합해
"쿼리를 미리 모아서 더 빠르게 처리하는 기법"을 소개합니다.

---

 

SqrtDecomposition, 제곱근분할, 블럭쿼리, 쿼리최적화, 파이썬알고리즘, 구간합, 세그먼트트리대안, 쿼리속도향상, 배열쿼리, SEO 최적화 10개