이 아이디어들을 직선이 아닌 좀더 일반적인 함수로 확장할수 있을까?
대상 함수셋을, 직선은 아니어도 되지만 두 함수는 최대 한 점에서만 만나는 조건을 만족한다고 바꿔보자.
그러면, 볼록껍질은 아니지만, 볼록껍질과 비슷한 특징을 갖는 그래프가 만들어진다. 특정 함수가 최솟값을 갖는 구간은 한개의 연속구간으로 제한된다. 그래서 볼록껍질처럼 각 함수가 최적이 되는 구간들을 구해두면 그 구간에 해당하는 함수에 대해서 값을 계산해줄 수 있었다.
직선일때는 어떻게 했더라 다시 정리해보자..
쿼리도 모노톤일 경우에는 함수들을 모노톤한 순서로 덱에 저장해놓기만 하면, 쿼리가 포함되는 구간을 amortized O(1)에 찾을수 있었다.
쿼리가 모노톤이 아닐때에는, 각 구간들을 명시적으로 구해놓은 뒤에, 이분탐색으로 쿼리가 포함되는 구간을 찾을수 있었다.
함수 추가 순서도 모노톤이 아닐때에는, 모노톤 스택을 이용해서 함수들을 모노톤한 순서로 저장하는 자체가 힘들었다. Li Chao트리를 보통 사용했다.
우선 함수 추가 순서가 모노톤하게 들어올 경우를 생각하자. 기본적으로는 스택의 top에 있는 함수와 교점을 '직선의 방정식'을 이용해서 계산해서 스택의 top에 있는 함수의 현재 관리 구간과 비교해서 처리한다.. 하지만 직선의 방정식을 이용해서 교점을 O(1)에 간단하게 구하는 방법을, 함수가 직선이 아닐때에는 쓸수 없다. 특정한 형태이면 교점을 수식으로 바로 구할수도 있겠지만.. 일반적인 경우에도 항상 사용가능한 방법은 이분탐색을 쓰는것이다.. 쿼리들이 자연수만 들어온다고 가정하면, 자연수 범위에서의 이분탐색을 이용해서 교점을 구할수 있다.
CHT에서 직선만 처리할때에도, 직선의 방정식을 사용하지 않고서 처리하는 구현법도 있긴 했다. 실수 사용을 피하기 위해서, 교점을 명확히 구하지 않고 처리했던 것인데, 이때는 대신 CCW를 이용해서 처리를 했다. 하지만 CCW 역시도 직선만의 특성을 이용한 것이기 때문에 일반적인 경우로 확장하는 것을 불가능하다.
이렇게 교점을 구해서, 유사 컨벡스헐을 만들어 낸다면, 이후 과정은 똑같다. 쿼리가 모노톤일때는 덱을 이용해서 처리해주면 된다. 이전에는 직선 추가를 O(1)에 했기 때문에 총 O(n+q)에 가능했지만, 지금은 직선 추가에 이분탐색을 써야해서 O(logn)이 걸리므로 총 시간은 O(nlogn+q)가 된다. 이 방식을 '단조 큐를 이용한 최적화' 라고도 부른다
쿼리가 모노톤이 아닐때도 직선일때와 똑같이 이분탐색을 이용해서 처리해주면 된다. 이러면 O((n+q)logn)이 된다.
Li chao tree를 사용해야 하는 경우는 이야기가 좀 다르다. Li chao tree는 이미 구현 자체가 직선에 방정식에 의존하지 않는다. 따라서 아무 코드 수정없이도 그냥 확장이 가능하다.
이분탐색을 써서 교점을 찾도록 코드를 수정하는것이 다 귀찮으면, 함수가 모노톤으로 들어오든 말든 그냥 Li chao tree를 써버리는 것도 가능한 방법이다. 지금은 덱으로 구현해도 어차피 리니어타임에 처리는 불가능하기 때문에, 시간복잡도 상으로 손해보는것도 없다. (이론상 복잡도는 그렇고 실제 처리시간은 느릴수 있지만..)