이 글에서는 Heavy-Light Decomposition의 구현, 이해를 해보도록 하겠습니다. Heavy-Light Decomposition 은 트리에서 경로 쿼리나 업데이트를 O(log^2N)에 할 수 있는 알고리즘입니다. 고등부 koi 2016 3번, nypc 2017 1519부문 5번으로 출제된 적이 있다고 합니다. Heavy Light Decomposition은 트리의 간선들을 Heavy Edge와 Light Edge로 구분하는 것을 의미합니다. 부모 정점에서 자식 정점으로 가는 간선이 있을 때, 자식의 서브 트리 크기가 부모의 서브 트리 크기의 절반 이상인 경우에는 그 간선을 Heavy Edge라고 하고, 나머지 간선들을 Light Edge라고 합니다. 그러면 한 정점에서 내려가는 Heavy ..
이 글에서는 Centroid Decomposition 의 구현, 이해를 해보도록 하겠습니다. Centroid Decomposition 은 트리에서 분할 정복을 수행하는 것이라고 생각하면 될 것 같습니다. 트리에서는 분할 정복을 하기 위해서 어떤 정점을 잡고 쪼개야 할지를 알려주는 것이 센트로이드 입니다. 일반적인 분할 정복 알고리즘과 같이, 트리에서 정점 하나를 지웠을 때 나뉘는 서브트리들의 크기가 모두 절반 이하가 되는 정점을 찾을 수 있다면, 알고리즘을 효율적으로 수행할 수 있을 것입니다. 그리고, 이 정점을 센트로이드라고 합니다. 모든 트리에서 이 센트로이드가 항상 존재한다는 것을 귀류법을 사용하여 증명할 수 있는데 이 글에서는 Centroid Decomposition 의 구현과 이해에 중점을 두고..
이 글에서는 BOJ 수열과 쿼리 5 문제를 해결하기 위한 Mo's Algorithm 에 대해서 설명하겠습니다. Mo's Algorithm 은 update가 주어지지 않는 쿼리에서 적용할 수 있는 알고리즘으로, 가끔 세그먼트 트리로는 해결하지 못하는 문제를 해결할 수 있는 알고리즘입니다. Mo's Algorithm 의 기본 아이디어는 쿼리의 순서를 원하는 대로 바꿀 수 있다는 것입니다. update가 주어지지 않는 쿼리이므로, 원하는 순서로 배치하여 처리하고, 다시 순서를 바꾸어 출력하면 됩니다. BOJ 수열과 쿼리 5 문제를 봅시다. 이 문제에서 이러한 아이디어를 생각해 봅시다. cnt[x] = 지금까지 센 x의 개수, L[x]는 x번째 쿼리의 첫 번째 수, R[x]는 x번째 쿼리의 두 번째 수 일때 각..
구간 쿼리 알고리즘 중 하나인 Lazy Propagation에 대해서 알아보겠습니다. 이 글은 세그먼트 트리에 대한 개념을 알고 있다는 전제 하에 작성되었습니다. //개인 공부용으로 작성하는 글입니다 일단, 구간[i, j]의 모든 값을 바꿀 수 있는 Lazy Propagation 의 작동 방식은 "업데이트를 게으르게 하는 것" 입니다. 업데이트를 필요할 때만 해서 시간 복잡도를 단축시킬 수 있는 것이라고 이해하면 될 것 같습니다. 구현에 대한 이해만 확실하게 한다면 어렵지 않게 사용할 수 있을 것입니다. 구현 이 글에서는 구간 [l, r]이 주어지면 해당 구간의 합을 구하거나, 구간 [l, r]의 모든 원소에 값 x를 더해줄 수 있는 세그먼트 트리를 구현하도록 하겠습니다. 1. init 함수 init 함..