GCD Segment Tree (1) 썸네일형 리스트형 163. GCD Segment Tree 연속된 원소들의 최대공약수를 빠르게 구하는 GCD 세그먼트 트리(GCD Segment Tree)에 대해 알아본다. 이 세그먼트 트리의 구성 방법은 간단하다. 리프 노드에 수열의 값들을 저장하고 부모 노드에 양 자식 노드에 저장된 값의 최대공약수를 저장하는 것이다. 다음과 같은 수열이 있다고 할 때, $$a = [48, 32, 24, 36, 18, 30, 20]$$ 이 수열을 GCD 세그먼트 트리로 표현하면 다음과 같다. 리프 노드가 빌 경우 $0$으로 채우면 된다. $x \ne 0$일 때 $\gcd(x, 0) = |x|$이므로 $20$과 $0$의 부모 노드에는 $20$이 저장된다. 또한 $\gcd(0, 0)$은 정의되지 않지만 일반적으로 그러는 것처럼 $0$으로 간주하면 된다. 이제 이 세그먼트 트리를 .. 이전 1 다음
