mo's algorithm 정리

[ganghe74]

sqrt decomposition인가? 복습하고 정리

[ganghe74]

https://www.quora.com/Whats-the-difference-between-square-root-decomposition-and-MOs-algorithm

mo's algorithm은 query에 전처리 작업(정렬)을 거쳐서, 이전 쿼리를 다음 쿼리를 해결하는데 이용한다는 개념이고,
sqrt decomposition은 배열을 sqrt 크기의 bucket 들로 분해한다는 개념

보통 mo's algorithm을 사용할때 sqrt 사이즈로 분해하기 때문에 Mo’s algorithm using Square Root Decomposition 라고 하는 듯 하다.

[ganghe74]

MO's Algorithm은 업데이트가 까다롭다는 단점이 있다.

[ganghe74]

Range Sum Query 를 해결하는 코드들을 커밋하였다.
사실 Range Sum Query는 Prefix Sum을 이용하면 각 쿼리들을 O(1)에 처리가 가능하다.

지금 있는 코드는 geeksforgeeks 사이트의 예제코드이고, 추후 PS용 숏코드로 수정할 예정