imos method (1) 썸네일형 리스트형 213. IMOS Method 펜윅 트리를 설명하면서 연습문제로 수열과 쿼리 21을 소개했다. 그리고 문제 해설에 구간 업데이트 + 점 쿼리를 점 업데이트 + 구간 쿼리로 변형할 수 있다고 했는데, 이 아이디어를 정형화한 IMOS법(IMOS Method)에 대해서 알아보기로 한다. IMOS법은 구간을 시작점과 끝점으로 분리하여 구간 처리를 점 처리로 대체하는 트릭으로, 구간이 여러 개 주어지고 특정 시점을 포함하는 구간의 수를 빠르게 구할 수 있는 방법이다. 수식을 써서 표현하면 다음과 같이 나타낼 수 있다.구간 $n$개가 존재하며, $i$번째 구간을 $[l_i, r_i]$로 나타낼 수 있다. $(l_i \le r_i)$$k$를 포함하는 구간의 수를 구하는 쿼리가 주어진다.여기서는 $l_i$와 $r_i$가 모두 $1$ 이상 $2n$ .. 이전 1 다음
