PBS

작동과정 및 복잡도

여러개의 binary_search 각각을 쿼리타입1 이라 하자. 줄여서 Q1

하나의 binary_search에서 판별함수(predicate)호출을 쿼리타입2 라고 하자. 줄여서 Q2

(오프라인쿼리가 가능해야한다) Q1을 일단 전부 모으자. 그리고 Q1의 개수=N이라 하자.

각 Q1마다 binary_search범위를 X라 할때 Q2는 logX개 존재한다.

이제 모든 Q1을 순회하면서 각각의 Q1마다 Q2하나씩을 처리하자. 이를 한번의 Round라고 부르자.

Q2처리에 O(1)만큼의 시간이 걸린다면 Q1배열을 최대 logX번 순회하게 되므로(=총 logX번의 Round) 총 복잡도는 O(N*logX*1)이다.

이때, 슬프게도 각 Q2를 처리하기 위해서 O(M)만큼의 시간이 걸리는 자료구조를 구축해야한다고 하자. 그러면 복잡도가 O(NMlogX)가 되서 좋지 않다.

다행히도 (Formal한 조건은 모르겠다)많은 경우에 자료구조가 다른쿼리들에 재사용될 수 있다! 이때 재사용하기 위해서는 Q1배열을 아무순서로 가지고 있으면 안되고 Q2의 쿼리위치값으로 정렬된 상태로 관리해줄 필요가 있다. 이렇게 자료구조를 쿼리를 순서대로 처리하면서 점진적으로 construct해가면서 한번의 자료구조 구축으로 N개의 Q1의 Q2하나씩을 처리해줄 수 있다면, 하나의 Q2는 amortized O(자료구조 쿼리복잡도)가 된다!! 즉, 라운드별로 일종의 스위핑처리를 통해 복잡도를 amortized하게 개선한거다. 그러면 총 복잡도는 amortized O(N*logX*자구쿼리 + 자구생성*logX)가 되고 보통의 자구쿼리 복잡도는 보통 자구생성에 비해 sub-linear하므로 복잡도가 훨씬 개선되었다.

메모

위처럼 라운드별 구간을 분할했을때, 끝(리프)에서는 구간길이가 power of 2형태가 아니라면 균형이진트리가 아니므로 d+1까지 업데이트 해줘야 정상적으로 계산된다. 그동안 [s,mid](mid,e)이렇게 구간나눠서 이상하게 코딩했었는데(심지어 반례 존재하는거같음 귀찮아서 따로 찾지는 않음) 위에서 말한대로 리프에서 d+1라운드값도 업데이트 해주면 [s,mid)[mid,e)로 나눠도 잘 작동한다. BOJ8217 첫제출이 이상한 코드고 두번째 제출이 정상적인 코드이니 확인해보자.

지금까지의 재귀구현방식 말고 while(true){}로 짜는걸 종종 봤는데, 그게 라운드별로 Sort+스위핑해주는 방식이다. 훨씬 직관적이니 그쪽으로 스타일 바꾸는게 좋을듯.

한줄요약: 여러번의 이분탐색을 batching(offline query)해서 라운드별 sweeping으로 한번에 처리한다.