[알고리즘] Prefix sum와 Segment Tree의 원리

1. 대수 구조의 정의

Monoid (단양군)

집합 $M$과 이항 연산 $\ast$의 쌍 $(M, \ast)$이 다음 두 조건을 만족하면 Monoid라고 한다.
1. 결합 법칙 (Associativity): $\forall a, b, c \in M, (a \ast b) \ast c = a \ast (b \ast c)$
2. 항등원 존재 (Identity): $\exists e \in M, \forall a \in M, e \ast a = a \ast e = a$

Group (군)

Monoid $(M, \ast)$가 다음 조건을 추가로 만족하면 Group이라고 한다.
3. 역원 존재 (Inverse): $\forall a \in M, \exists a^{-1} \in M, a \ast a^{-1} = a^{-1} \ast a = e$
예로, $<\Z,+>$, $<\Z_n^*,*>$ 는 Group 이다.

---

2. Prefix Sum의 정의와 Group에 의한 $O(1)$ 증명

정의

수열 $A=\ <a_1, a_2, \dots, a_n>\ \subset G$에 대하여 Prefix Sum $S$는 다음과 같이 재귀적으로 정의된다.

구간 쿼리 증명 (Group)

구간 $[l, r]$의 연산 결과 $P_{l,r} = a_l \ast a_{l+1} \ast \dots \ast a_r$이라 할 때, $s_r = s_{l-1} \ast P_{l,r}$이 성립한다.
$(G, \ast)$가 Group이면 역원 $s_{l-1}^{-1}$이 존재하므로,

결합 법칙에 의해

따라서 $P_{l,r} = s_{l-1}^{-1} \ast s_r$로 $O(1)$ 계산이 가능하다.

예시

수열 $A =\ <a_1, a_2, \dots, a_n>\ \in \mathbb{Z}^n$ 와 쿼리 $[l, r]$ 에 대해 $\sum_{i=l}^{r}a_i$ 를 구한다고 하자.
$<\Z,+>$는 Group이므로 Prefix Sum $S$를 정의할 수 있다.
$+$ 연산자에서 정수 $a$의 역원은 $-a$이므로 $s_{l-1}^{-1} = -s_{l-1}$ 이다.

스위핑, 차분배열 또한 역원을 사용하므로 Prefix Sum과 비슷하다.

---

3. Segment Tree와 Monoid의 수학적 증명

Segment Tree는 구간 $[l, r]$을 서로소인 부분 구간들의 합집합으로 분할한다.

Group이 아닌 Monoid로 충분한 이유

임의의 구간 $[L, R]$이 Segment Tree의 노드 집합 $\{v_1, v_2, \dots, v_k\}$에 의해 관리되는 부분 구간들의 합집합으로 분할된다고 가정한다.

이때 각 노드 $v_m$에 저장된 값을 $Val(v_m)$이라 하면, 전체 구간의 값은 다음과 같다.

1. 결합 법칙의 필연성:
   Segment Tree는 완전 이진 트리 구조로 연산을 수행하므로, 계산 순서가 $((v_1 \ast v_2) \ast v_3) \dots$와 같이 고정되지 않고 트리의 형태에 따라 임의의 괄호 배치가 발생한다.
   $\forall v_i, v_j, v_k$, $(v_i \ast v_j) \ast v_k = v_i \ast (v_j \ast v_k)$ 가 만족되어야만 트리의 분할 방식에 관계없이 동일한 값을 보장한다.

2. 역원의 불필요성:
   Segment Tree는 $s_r$에서 $s_{l-1}$을 제거하는 방식이 아니라, 필요한 구간들만을 합성하여 값을 구축한다. 따라서 $x \ast x^{-1} = e$와 같은 역원 연산이 논리적으로 필요하지 않다.

3. 항등원의 역할:
   쿼리 범위 밖의 노드를 처리할 때 $v = v \ast e$ 연산을 수행함으로써 알고리즘의 일관성을 유지한다.