모노이드(Monoid)란? 세그먼트 트리를 다양한 쿼리로 일반화하는 방법

 

모노이드(Monoid)란? 세그먼트 트리를 다양한 쿼리로 일반화하는 방법

세그먼트 트리는 원래 구간 합 구하기를 위해 설계된 자료구조지만,
구간 합뿐만 아니라 최댓값, 최솟값, 최대공약수(GCD), XOR, 곱 등 다양한 쿼리로 확장할 수 있습니다.

이 확장의 핵심 이론이 바로 **모노이드(Monoid)**입니다.

이번 글에서는 모노이드 개념, 세그먼트 트리 일반화,
그리고 최대값, GCD, XOR 쿼리로 확장하는 실제 예제까지 쉽고 명확하게 정리합니다.

---

✅ 모노이드(Monoid)란 무엇인가?

어떤 집합 S와 **이항 연산 ∘**가 있을 때,
아래 두 조건을 모두 만족하면 (S, ∘)는 모노이드입니다:

1. 결합 법칙(Associative Law)
   • (a ∘ b) ∘ c = a ∘ (b ∘ c)
   • 예시: 덧셈, 최댓값, 최솟값, GCD, XOR
2. 항등원(Identity Element) 존재
   • 어떤 a에 대해: a ∘ e = e ∘ a = a인 e가 존재해야 함
   • 예시:
     • 덧셈의 항등원 = 0
     • 곱셈의 항등원 = 1
     • 최댓값 쿼리의 항등원 = -∞
     • 최솟값 쿼리의 항등원 = +∞
     • GCD 항등원 = 0
     • XOR 항등원 = 0

---

🧠 세그먼트 트리를 모노이드 기반으로 일반화하면?

• 원소 타입: 어떤 자료형이든 가능 (int, float 등)
• 연산 방법: ∘ 연산만 주어지면 동작
• 항등원: 빈 구간이나 범위 벗어남을 처리할 때 사용

즉,
"합"을 더하는 트리
→ "최대값을 구하는 트리", "최소값을 구하는 트리", "GCD를 구하는 트리" 등으로 쉽게 바뀔 수 있습니다.

---

🛠 Python 세그먼트 트리 모노이드 버전 (클래스 템플릿)

class SegmentTree:
    def __init__(self, data, op, e):
        self.N = len(data)
        self.tree = [e] * (2 * self.N)
        self.op = op  # 이항 연산 함수
        self.e = e    # 항등원

        for i in range(self.N):
            self.tree[self.N + i] = data[i]
        for i in range(self.N - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, index, value):
        index += self.N
        self.tree[index] = value
        while index > 1:
            index >>= 1
            self.tree[index] = self.op(self.tree[index << 1], self.tree[index << 1 | 1])

    def query(self, l, r):  # [l, r) 구간 쿼리
        l += self.N
        r += self.N
        res_left = self.e
        res_right = self.e
        while l < r:
            if l & 1:
                res_left = self.op(res_left, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_right = self.op(self.tree[r], res_right)
            l >>= 1
            r >>= 1
        return self.op(res_left, res_right)

---

✅ 다양한 쿼리 확장 실습

1. 구간 합 트리 (Sum Segment Tree)

arr = [5, 8, 6, 3, 2, 7, 2, 6]
st_sum = SegmentTree(arr, op=lambda a, b: a+b, e=0)

print(st_sum.query(2, 5))  # 출력: 6+3+2 = 11

---

2. 구간 최댓값 트리 (Max Segment Tree)

st_max = SegmentTree(arr, op=max, e=float('-inf'))

print(st_max.query(1, 6))  # 출력: 8 (최대값)

---

3. 구간 최소공약수(GCD) 트리 (GCD Segment Tree)

from math import gcd

st_gcd = SegmentTree(arr, op=gcd, e=0)

print(st_gcd.query(0, 4))  # 출력: GCD(5,8,6,3) = 1

---

4. 구간 XOR 트리 (XOR Segment Tree)

st_xor = SegmentTree(arr, op=lambda a, b: a ^ b, e=0)

print(st_xor.query(0, 8))  # 전체 XOR 결과

---

📘 모노이드 세그먼트 트리 적용 가능 문제

반응형

분야 설명

누적합 쿼리	합, XOR, 모듈로 누적합 등
구간 최댓값/최솟값	RMQ(Range Minimum/Maximum Query) 문제
구간 GCD 쿼리	공약수 계산 최적화
수학적 쿼리	특정 수성질 기반 쿼리 (ex. AND, OR, XOR)

---

📌 결론 및 요약

• 모노이드는 "결합법칙 + 항등원"만 만족하면 어떤 연산이든 가능
• 세그먼트 트리를 모노이드로 일반화하면 코드를 한 번 작성해 다양한 문제에 재활용 가능
• 합뿐 아니라 최댓값, 최솟값, GCD, XOR 같은 다양한 쿼리도 빠르게 지원

👉 다음 글에서는 모노이드 세그먼트 트리에 Lazy Propagation을 결합하여
구간 업데이트 + 다양한 쿼리를 동시에 처리하는 고급 테크닉을 다룰 예정입니다.

---

📚 참고자료 및 출처

• 『알고리즘 문제 해결 전략』 (구종만)
• Competitive Programming 3
• CP-Algorithms – Segment Trees and Monoids

---

 

모노이드, monoid, 세그먼트트리일반화, 다양한쿼리, 최대공약수, XOR쿼리, 파이썬 알고리즘, 자료구조 최적화, 트리자료구조, SEO 최적화 10개

---