구간 트리의 성립 조건 ★

이 글에서는 구간 트리(segment tree), 펜윅 트리(fenwick tree), 느리게 갱신되는 구간 트리(segment tree with lazy propagation)들이 성립하는 조건을 알아볼 것이다.

 

다만, 이 글에는 한계가 존재한다. 구간 트리를 하나의 Black-Box(기능은 알지만 작동 원리를 이해할 수 없는 복잡한 기계 장치나 시스템, 물체)로 바라보기 때문에 직사각형들의 합집합의 넓이를 구하는 문제와 같이 구간 트리의 구조를 변형시키는 문제에는 이 글의 내용이 적용이 되지 않을 수 있다.

 

기본

질의응답의 대상인 배열은 $[a_1,a_2,\ldots,a_n]$이다.

배열 속 원소들을 포함하는 집합 $S$, 원소들 간의 이항 연산 $*$, 갱신 함수의 집합 $F$가 있다.

이때, 당연히 $*:S\times S\mapsto S$이고 $\forall f\in F$, $f:S\mapsto S$이다.

 

구간 트리

구간 트리는 집합과 이항 연산, 갱신 함수 집합의 쌍에 대해서 일차원 배열의 구간 질의와 원소 갱신을 지원하는 자료구조이다.

• 질의 과정: $\text{query}(\ell,r)$에 대해 $a_\ell * a_{\ell+1} * \cdots * a_r$을 반환한다.
• 갱신 과정: $\text{update}(k,i)$에 대해 $a_k\leftarrow f_i(a_k)$를 처리한다.

항등원

대부분의 경우에 항등원이 존재한다. –필자는 여태까지 항등원이 존재하지 않는 사례는 확인하지 못했다– 항등원이 존재하지 않을 경우에도 가능하긴 하지만 구현이 좀 까다로울 것이다. 그러니 그냥 항등원이 존재하는 것을 전제하도록 하자.

 

결합법칙

결합법칙이 만족해야 자식 노드로 현재 노드를 구성할 수 있다. 즉, $(a_\ell * \cdots * a_m) * (a_{m+1} * \cdots * a_r) = a_\ell *\cdots * a_r$가 되어야 한다는 뜻이다.

 

성립 조건 요약

• 항등원이 존재한다.
• 결합법칙을 만족한다.

 

펜윅 트리

펜윅 트리는 구간 트리에 역연산을 잘 활용할 수 있는 경우 사용하는 더 가벼운 자료구조이다.

 

질의 과정의 정당성

펜윅 트리는 길이가 $2^k$꼴인 구간들을 결합하여 구성하는데, 그렇게 나온 구간은 접두사 부분이 된다. 따라서 $a_\ell *\cdots * a_r$에 대해 $a_1*\cdots*a_r$의 값에서 $a_1*\cdots*a_{\ell-1}$의 값을 소거하는 방식으로 구성된다.

이때, 역연산을 통해 소거하므로 역원(inverse)이 존재해야 한다. 그리고 교환법칙을 만족해야 하는데, 이는 $a_1*\cdots*a_r\ *\ \text{inv}_{\langle S,*\rangle}(a_1*\cdots*a_{\ell-1})$을 통해 $a_\ell * \cdots * a_r$을 계산하기 때문이다.

 

갱신 과정의 정당성

$\ell\le k\le r$인 펜윅 트리에서 관리하는 구간 $[\ell,r]$들의 값을 $a_\ell*\cdots *a_k* \cdots *a_r$에서 $a_\ell*\cdots *f(a_k)* \cdots *a_r$로 바꿔야 한다. 이때, $a_\ell*\cdots *f(a_k)* \cdots *a_r=f(a_\ell*\cdots*a_k*\cdots *a_r)$이라는 것이 보장되어야 한다. 이는 $f(x*y)=f(x)*y$ 정도로 정리할 수 있다.

이는 상당한 제약 조건이다. 따라서 덧셈이나 비트 XOR 연산 말고는 잘 사용되지 않는다.

 

성립 조건 요약

• 항등원이 존재한다.
• 결합법칙을 만족한다.
• 역원이 존재한다.
• 교환법칙을 만족한다.
• $f(x*y)=f(x)*y$를 만족한다.
  

 

느리게 갱신되는 구간 트리

느리게 갱신되는 구간 트리는 느긋한 전파(lazy propagation)를 통해 원소 갱신뿐만 아니라 구간 갱신까지 지원하는 자료구조이다.

• 질의 과정: $\text{query}(\ell,r)$에 대해 $a_\ell * a_{\ell+1} * \cdots * a_r$을 반환한다.
• 갱신 과정: $\text{update}(\ell,r,i)$에 대해 $(a_{l},a_{\ell+1},\ldots,a_r) \leftarrow (f_i(a_\ell),f_i(a_{\ell+1}),\ldots,f_i(a_r))$를 처리한다.

잘 알려져 있듯이, 느긋한 전파는 실제로 모든 원소를 새로운 원소로 바꾸지 않는다. 대신, 갱신의 일부를 미루어 두었다가 질의가 들어올 때 필요한 일부만 변경을 하여 효율적으로 답한다. 단, 질의와 갱신 모두 현재 확인하는 노드의 구간에 대해서만큼은 항상 갱신을 반영한 정확한 값을 가진다는 것에 유의하자.

 

구간에 대응되는 값을 가지는 배열을 이용하자.

표현의 편의를 위해 구간 트리의 하나의 노드가 나타내는 구간 $[\ell,r]$에 대해, $\text{value}_{\ell,r}:=a_\ell*\cdots*a_r$.

모든 $\text{value}_{\ell,r}$은 최초에 항등원으로 초기화되어있다.

 

전파에 필요한 구간 트리의 노드에 대응되는 배열을 이용하자.

표현의 편의를 위해 구간 트리의 하나의 노드가 나타내는 구간 $[\ell,r]$에 대해, $\text{lazy}_{\ell,r}:=a_\ell,\ldots,a_r$에 적용하려고 대기 중인 함수들을 순서대로 합성한 합성함수. 참고로, 함수의 합성은 결합법칙을 항상 만족한다.

모든 $\text{lazy}_{\ell,r}$은 최초에 항등함수로 초기화되어있다.

 

느긋한 전파 과정

현재 노드에는 미뤄둔 갱신을 처리한다. 엄밀히는, 원래 $\text{value}_{\ell,r} = a_\ell*a_{\ell+1}*\cdots*a_r$로 설정되어 있던 값을 $\text{value}_{\ell,r} \leftarrow \text{lazy}_{\ell,r}(a_\ell)*\text{lazy}_{\ell,r}(a_{\ell+1})*\cdots*\text{lazy}_{\ell,r}(a_r)$로 바꿔준다.

두 개의 자식 노드에는 $(\text{lazy}_{\ell,m},\text{lazy}_{m+1,r})\leftarrow (\text{lazy}_{\ell,r} \circ \text{lazy}_{\ell,m}, \text{lazy}_{\ell,r}\circ \text{lazy}_{m+1,r})$을 함으로써 당장 필요하지 않은 갱신을 미뤄둔다.

현재 노드에 미뤄둔 갱신을 전부 처리했으므로 $\text{lazy}_{\ell,r}$를 항등함수로 바꿔준다.

 

갱신 과정의 정당성

조상 노드를 먼저 방문한 뒤 느긋한 전파를 수행하므로, 조상 노드들에는 미뤄둔 갱신이 없다.

갱신 구간에 포함된 노드에 $\text{lazy}_{\ell,r}\leftarrow f\circ \text{lazy}_{\ell,r}$를 처리한 뒤, 느긋한 전파를 한다.

각 값들이 갱신이 반영된 정확한 상태이므로 구간을 합치며 다시 계산할 때에 올바른 값이 이용된다.

 

질의 과정의 정당성

갱신 구간에 포함된 노드에 미뤄둔 갱신이 있으면 느긋한 전파를 한다.
각 값들이 갱신이 반영된 정확한 상태이므로 구간을 합치며 다시 계산할 때에 올바른 값이 이용된다.

 

성립 조건 요약

• 항등원이 존재한다.
• 결합법칙을 만족한다.
• $\text{lazy}_{\ell,r}$을 충분히 작은 시공간 내에 사용할 수 있다.
  
• 충분히 빠른 시간 내에 $\text{value}_{\ell,r}$를 $a_\ell*a_{\ell+1}*\cdots*a_r$에서 $\text{lazy}_{\ell,r}(a_\ell)*\text{lazy}_{\ell,r}(a_{\ell+1})*\cdots*\text{lazy}_{\ell,r}(a_r)$로 바꿀 수 있다.