Mo's Algorithm (1) 썸네일형 리스트형 170. Mo's Algorithm 이번에는 제곱근 분할법을 수열에 적용하는 방법을 알아보자. 모스 알고리즘(Mo's Algorithm)은 제곱근 분할법을 이용하여 세그먼트 트리 등의 자료 구조로 처리하기 어려운 쿼리를 처리하는 방법이다. 제곱근 분할법을 수 자체에 적용할 때는 제곱근 이하와 이상, 두 부분을 따로 다루었는데 제곱근 분할법을 길이가 $n$인 수열에 적용하면 $\sqrt{n}$ 정도의 길이를 갖는 $\sqrt{n}$개의 구간을 기준으로 접근하게 된다는 차이점이 있다는 것은 제곱근 분할법을 수에 적용하는 방법을 소개할 때도 언급했다. 그러면 모스 알고리즘의 작동 방법을 알아보자. 여기서 $\sqrt{n}$은 전부 근삿값이며 적당히 가까운 정수를 사용하면 된다. 또한 처리하는 쿼리들은 구간 $[l, r]$로 나타낼 수 있으며 한.. 이전 1 다음
