모스알고리즘이란? 모스 알고리즘은 업데이트가 없는 구간 쿼리들을 처리하는 알고리즘이다. 기본 아이디어는 업데이트가 없기 때문에 '앞에서 계산된 값을 최대한 활용하자'이다. 특히 조회만 하는 경우는 쿼리의 순서를 자유롭게 바꿀 수 있는 환경에서 미리 계산된 값을 다시 이용할 수 있을 것이다. 이전에 살펴 보았던 제곱근분할법(https://wondangcom.tistory.com/2721) 을 이용하여 모스알고리즘을 구현 할 수 있는데 이 알고리즘으로 해결할 수 있는 문제는 원소의 수정은 없고 구간 내에서 어떤 결과를 찾는 종류의 쿼리만 있는 문제이다. 그렇다면 기존 문제보다 활용범위가 좁은 것은 아닐까? 간혹 세그먼트 트리 등을 이용해서 해결하지 못하는 경우가 발생한다. 이러한 문제 유형은 아래에서 살펴 ..