원소들을 효율적으로 관리해야할 일이 있을때 우리는 어떤 전략을 선택해야할까? 원소들을 효율적으로 관리하는 방법은 여러가지가 있다. 이번에는 그 중 하나인 Sqrt Decomposition에 대해 알아보도록 하자. Sqrt Decomposition에서 Sqrt는 Square root의 약자다. 이를 우리나라 말로 번역하자면 평방분할이라고 한다. 하지만 의미적으로 별로 와닿지 않는다고 생각하기 때문에 Sqrt Decomposition이라고 하겠다. 연속적인 원소들을 하나의 묶음으로 Sqrt Decomposition의 기본 아이디어는 정말 간단하다. 연속적인 원소들을 하나의 묶음으로 생각하자는 것이다. 이 때 한 묶음의 크기는 보통 \(\sqrt N\)으로 잡는다.(그래서 Square root라는 ..
