[구간최대/최소/구간합] Sqrt Decomposition과 Segment Tree

배열이 업데이트 되면서서 구간 최대, 최소, 합을 구하는 문제를 효율적으로 풀기 위한 Sqrt Decomposition과 Segment Tree 알고리즘에 대하여 알아보겠습니다.  

 

---

Square Root Decomposition은 특정 유형의 쿼리 및 업데이트 작업을 효율적으로 처리하기 위한 기법으로, 주로 정적 배열에서 동작합니다. 이 기법은 배열을 고정된 크기의 블록으로 나누어 각 블록에 대한 일부 계산을 미리 수행하여 시간 복잡도를 줄이는 방식으로 동작합니다.

1. 블록 크기

• 배열의 길이를 n이라 할 때, 각 블록의 크기는 √n으로 설정합니다. 이는 시간 복잡도를 O(√n)으로 유지하기 위해서입니다.
• Python 코드에서는 math.ceil(math.sqrt(n))을 사용하여 블록 크기를 정수로 계산합니다.

2. 블록 구조

• 배열을 √n 크기의 블록으로 나누며, 각 블록의 합을 별도로 저장합니다.
• 블록의 인덱스는 i // block_size로 계산됩니다.
  • 예: 배열 [1, 3, 5, 7, 9, 11]을 block_size=3으로 나누면,
    블록 0: [1, 3, 5] → 합: 9
    블록 1: [7, 9, 11] → 합: 27

3. 쿼리 처리

• 쿼리 범위 [l, r]에 대해:
  1. 시작점 l부터 블록 경계까지의 값은 직접 계산.
  2. 완전히 포함된 블록의 합은 블록 합을 바로 사용.
  3. 남은 범위 [r]의 값은 다시 직접 계산.

4. 업데이트 처리

• 배열 값이 변경되면 해당 블록의 합도 갱신해야 합니다.
• 예를 들어, 인덱스 i가 블록 0에 속하면, 블록 0의 합에서 기존 값을 빼고 새 값을 더해 갱신합니다.

---

시간 복잡도

• 쿼리: O(√n) (최대 2√n 만큼의 작업)
• 업데이트: O(1) (블록 합만 갱신)

구간 합 예제 코드

import math


class SqrtDecomposition:
    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr)
        self.block_size = int(math.sqrt(self.n))  # 블록 크기
        self.blocks = [0] * (self.n // self.block_size)  # 각 블록의 합 저장

        # 각 블록의 합 계산
        for i in range(self.n):
            self.blocks[i // self.block_size] += self.arr[i]

    def query(self, l, r):
        """
        배열에서 인덱스 [l, r] 범위의 합을 반환합니다.
        """
        sum_ = 0

        # 시작 지점에서 블록 경계를 벗어나지 않는 범위 처리
        while l <= r and l % self.block_size != 0:
            sum_ += self.arr[l]
            l += 1

        # 블록 단위로 합 계산
        while l + self.block_size - 1 <= r:
            sum_ += self.blocks[l // self.block_size]
            l += self.block_size

        # 남은 마지막 범위 처리
        while l <= r:
            sum_ += self.arr[l]
            l += 1

        return sum_

    def update(self, index, value):
        """
        배열의 특정 인덱스 값을 업데이트하고 관련 블록 값을 갱신합니다.
        """
        block_index = index // self.block_size
        self.blocks[block_index] += value - self.arr[index]
        self.arr[index] = value


# 사용 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15]
sd = SqrtDecomposition(arr)

# 쿼리: 인덱스 1부터 6까지의 합
print("Query(1, 6):", sd.query(1, 6))  # 출력: 50

# 업데이트: 인덱스 3의 값을 10으로 변경
sd.update(3, 10)
print("Query(1, 6) after update:", sd.query(1, 6))  # 출력: 53

Sqrt Decomposition도 충분히 효율적인 알고리즘이지만, 배열이 블록 크기가 고정되어 있어 배열 크기가 매우 크거나 작을 때 비효율적일 수 있다는 단점이 있습니다. 해당 알고리즘은 중소 규모의 문제에 적합하며, 좀 더 복잡하거나 큰 배열을 다룰 때에는 Segment Tree가 효과적입니다. 

 

---

Segment Tree는 이진 트리 형태로 배열의 특정 구간에 대한 연산 결과(예: 합, 최소값, 최대값 등)를 저장합니다.

구조

1. 리프 노드(Leaf Node):
   • 입력 배열의 각 요소를 나타냅니다.
   • 배열의 크기가 n이라면, 트리의 리프 노드는 n개입니다.
2. 내부 노드(Internal Node):
   • 배열의 특정 구간을 나타내며, 해당 구간의 연산 결과를 저장합니다.
   • 예: 구간 합 트리라면, 내부 노드에 자식 노드 구간 합이 저장됩니다.
3. 트리의 크기:
   • Segment Tree는 배열의 크기 nnn에 대해 최대 4n크기의 배열에 저장됩니다.
   • 이는 트리의 균형성과 이진 분할 방식에서 발생하는 여유 공간 때문입니다.

일반적으로 이진트리 기반으로 구현됩니다.  

시간 복잡도

1. 구간 질의: O(log⁡n)
2. 값 업데이트: O(log⁡n)
3. 트리 빌드: O(n)

# 구간의 최대값을 효율적으로 수행하는 세그먼트 트리
class SegmentTreeMax:
    def __init__(self, arr, N):
        self.tree = [0] * 2 * N
        self.n = N
        for i in range(N):
            self.tree[N+i] = arr[i]
        # pre-calculate tree
        for i in range(N-1, 0, -1):
            # i<<1 = i*2, i<<1|1 = i*2+1
            self.tree[i] = max(self.tree[i<<1], self.tree[i<<1|1])

    def update(self, index, value):
        i = index + self.n
        self.tree[i] = value
        while i > 1:
            # i^1 = leaf 노드(원본 data)의 형제/자매 노드를 의미
            self.tree[index>>1] = max(self.tree[i], self.tree[i^1])
            i >>= 1

    def query(self, l, r):
        l += self.n; r += self.n; _res = 0
        while l <= r:
            # left가 홀수인 경우: 최댓값 정보 수집 후 1 증가
            if l & 1:
                _res = max(_res, self.tree[l])
                l += 1
            # right가 짝수인 경우: 최댓값 정보 수집 후 1 감소
            if not (r & 1):
                _res = max(_res, self.tree[r])
                r -= 1
            # 부모 노드로 올라감
            l >>= 1
            r >>= 1
        return _res​

ㄷ

두 알고리즘 모두 build - query - update 크게 3개의 축으로 구분됨에 유의하면 더 기억하기 쉽습니다!