-
jthis's profile image
jthis
June 23, 2023
Variation of Mo's Algorithm 2
안녕하세요 jthis 입니다. 이 글에서는 Variation of Mo’s Algorithm 1에 이어 또다른 Mo’s Algorithm의 variation에 대해 소개하겠습니다. Mo’s Algorithm with Update Mo’s Algorithm은 쿼리 문제를 효율적으로 해결하는 알고리즘입니다. 하지만 일반적인 Mo’s Algorithm은 업데이트 연산을 처리할 수 없어, 해당 제약으로 인해 사용하기 어려운 경우가 있습니다. 이런 상황에서 사용할 수 있는 3D Mo’s Algorithm이라고도 불리는 Update Mo’s Algorithm에 대해 소개하고자 합니다. 예를 들어, 쿼리문제를 생각해 봅시다. 이 문제에서는 다음과 같은 연산이 주어집니다: 1 i x: $A_i$를 x로...
-
jthis's profile image
jthis
February 17, 2023
Variation of Mo's Algorithm 1
안녕하세요 jthis 입니다. 이 글에서는 Mo’s Algorithm의 variation에 대해 소개하겠습니다. Mo’s Algorithm Mo’s Algorithm은 구간 쿼리를 offline으로 해결하는 알고리즘입니다. Mo’s Algorithm에 대한 자세한 설명은 Mo’s Algoithm에서, Mo’s Algorithm을 사용한 트리의 서브 트리에 대한 쿼리나 경로에 대한 쿼리는 Mo’s on Tree 에서 찾아보실 수 있으니 읽고 오시면 도움이 될 것입니다. Mo’s Algorithm with Rollback Mo’s Algorithm을 사용할 때 원소를 제거만 하거나 삽입만 하고 싶다는 생각을 해보신 적 있으실 겁니다. 간략하게 설명하자면 원소를 삽입하는 연산만 하고 싶을...