ps:cht
목차
볼록 껍질을 이용한 최적화
- [정리 예정]
- 제대로 정리를 해야 되지만, 급한대로 3줄요약부터 하자..
- f_i(x) = a_i * x + b_i 형태의 1차함수들이 N개 있을때, 어떤 x=k에 대해서 min_i{f_i(k)} 값을 계산하는 것을 O(N)보다 빠르게 할수 있다. 이것이 기본 아이디어이다.
- 여기에 덧붙여서 1차함수들을 추가하는 것도 빠르게 할수 있다.
- 구체적으로는 케이스에 따라 다르다. 아래로 갈수록 느리다
- 함수 추가가 기울기가 단조감수하는 순서로 이루어지면, N개의 함수를 추가하는데에 amortized O(N)에 처리 가능. (스택)
- min값을 계산하는 쿼리의 x값들이 단조증가하는 순서로 들어온다면, Q개의 쿼리를 역시 amortized O(N+Q)에 처리 가능
- min값을 계산하는 쿼리의 x값들이 랜덤순서로 들어온다면, 1개의 쿼리를 O(logN), Q개의 쿼리를 O(QlogN)에 처리 가능 (이분탐색)
- 함수 추가가 기울기가 랜덤한 순서로 이루어지면, BBST나 리차오트리를 써야 한다. 하지만 파이썬에서 BBST 솔루션은 느리다.
- 들어올 쿼리들을 미리 안다면, 정적 리차오 세그트리를 쓸수 있다. 좌표압축에 O(QlogQ)를 한 후에 세그트리를 만들면, 라인 추가, min 쿼리 모두 O(logQ). 총 O((N+Q)logQ)
- 들어올 쿼리들을 미리 알지 못한다면, 동적 리차오 세그트리를 쓴다. 라인 추가, min 쿼리 모두 O(logN). 총 O((N+Q)logN)..인데 상수값이 정적 세그트리에 비해서 크다.
- 따라서 오프라인 처리가 가능하면 적어도 함수들은 기울기순으로 정렬한 다음에 스택에 저장하는 것이, 함수를 정렬하는 O(NlogN) 시간을 포함해도 훨씬 빠르다.
- 쿼리들도 O(QlogQ)에 정렬해서 총 O(QlogQ+N+Q)=O(N+QlogQ)에 할지, 그냥 쿼리들은 정렬 않고 O(N+QlogN)에 처리할지는 속도에 큰 차이는 없는것 같다.
- 이 형태는 DP식을 최적화 할때에도 유용하게 사용된다. DP[i] = min_{j<i} {a[j]*b[i]+c[j]+d[i]} 형태이면 이 최적화를 쓸 수 있다.
- 보통은 c[j]가 dp[j]를 포함하는 형태로 나오지만 a[j]에 포함되어도 상관없다.
- 이 경우에는 쿼리를 한번 해서 DP[i]를 구하고, 구한 dp값에 따라 정의되는 직선을 다시 추가하고 하는 식이므로, 쿼리의 갯수와 추가하는 직선의 갯수가 같다.
- 무식하게 계산하면 O(n^2)이지만, 이 최적화를 사용함으로써 a[j]와 b[i]가 모두 정렬되어있으면 O(n), 그렇지 않으면 O(nlogn)에 계산할수 있다.
- 쓰고나니 3줄이 아니군.. 뭐 어차피 제대로 다시 정리할 것이긴 하다..
정리안됨
- 급한대로 3줄요약은 해놨으니까.. 이제 아이디어들을 정리가 안됐더라도 일단 적어놓고 보자 (까먹기 전에!)
- 참고자료
- (min쿼리 문제를 기준으로) 기울기가 감소하는 순으로 라인이 추가되면
- 쿼리의 x값이 계속 증가하면, ⇒ 라인을 덱으로 관리. n개 라인 q개 쿼리를 O(n+q)에 처리
- 쿼리의 x값이 증가하지 않으면 ⇒ 라인을 스택으로 관리. 쿼리를 이분탐색으로 처리. n개 라인 q개 쿼리를 O(n+qlogn)에 처리
- 오프라인 쿼리가 가능하면 그냥 쿼리를 정렬해서 쓰는게 더 나을수도 있다
- 추가되는 라인들의 기울기가 정렬되지 않은 상태
- 라인을 bbst(linecontainer(코드)) 이나 세그트리 (li-chao tree)로 관리. n개라인 q개 쿼리를 O((n+q)logn)에 처리
- 또는 정렬된 리스트와, 사이즈 sqrt(n)의 정렬안된 리스트로 나누어서 관리하는 방법 n개라인 q개 쿼리를 O((n+q)sqrt(n))에 처리
- line container은 c++로 만들어진 코드. 구현이 짧지만 복잡하다. 속도가 빠르다. std::multiset을 사용한다
- li-chao tree는 세그에 직선을 박은것. linecontainer보다는 느리지만 이해하기는 쉽다
- sqrt방식은 자료구조가 필요없다. 시간 복잡도가 nsqrt(n)으로 좀더 떨어지긴 하지만, nlogn방식보다 상수가 작아서 할수 있다고 한다만.. python에서는 어떨지..
구현관련
- 라인을 스택이나 덱으로 관리할 경우
- 교점을 실수형으로 저장해서 쓰는 구현법과, 직선 방정식만 저장해서 그때그때 계산해서 쓰는 방법이 있다
- 실수 오차는 항상 머리아픈 문제이지만, 이 경우에는 실수형으로 교점을 저장해서 처리해도 웬만하면 문제 없다고 하긴 한다.
- 흔히 찾을수 있는 것은 실수형을 쓰는 구현.
- 실수형을 안쓰는 구현은
- https://blog.myungwoo.kr/108 (이쪽은 코드가 지저분해서 이해하기 좀 어렵다)
- 라인을 추가할때 back쪽 라인을 제거해야 하는지를 처리하기 위해서 CCW을 돌린다.
- 덱을 쓸경우, 쿼리하면서 front쪽 라인을 제거해야 하는지를 처리하기 위해서, f()값을 계산해서 비교한다
- 교점을 직접적으로 구하지 않는다.
- 사소한 차이들
- 교점을 같이 저장하는 구현에서는, max쿼리를 처리하는 문제도 코드 수정 없이 처리할수 있다. 기울기가 증가하는 순으로 넣어주기만 한다면, 똑같은 코드가 이번에는 max값을 리턴한다.
- 하지만… 동일한 기울기가 들어오는 것을 처리하게 된다면, 여기서도 결국 max쿼리일때랑 min쿼리일때의 코드가 결국 달라져야 한다
- 기울기가 decreasing order가 아니라 non-increasing order로 들어올때..
- 교점을 같이 저장하는 방식에서는 따로 처리해줘야 한다. (기울기가 같으면 y절편을 비교해서 처리하는 로직 필요)
- 교점을 저장하지 않는 방식에서는 따로 처리 안해줘도 된다.
- 속도면에서 실수형을 쓰는 구현이 많이 빨랐다.
- 이쪽으로 사용하자!
- 라인을 스택이나 덱으로 관리할수 없는 경우
- lineContainer을 마이그레이션 해서 쓰기에는 내장 bbst가 없다는 문제가 크다.. treap같은걸로 대체해서 처리하면? 그러면 결국, 짧은 코드와 빠른 속도라는 장점이 다 사라질거 같은데…. 흠..
- li-chao tree를 쓰는 경우?
- 세그트리에 직선을 박은게 리차오 트리인데. 일단 기본적으로는 다이나믹 세그트리를 기준으로 한다.
- 당연히 속도가 좀 느려질건 감수해야 한다.
- 근데, 쿼리로 들어올 좌표들을 미리 알고 있다면 좌표압축 테크닉을 적용해서 그냥 정적 세그트리로 만들수도 있다. 그리고 비재귀로 짤수도 있다. 하지만 이 방식으로 설명한 자료는 거의 찾기가 힘들다.. 그리고 비재귀이긴 하지만 bottom-up인것은 또 아니다..
- yosupo의 상위 코드들은 다 이쪽 방식이다
- 근데!!! Li Chao tree가 꼭 직선만 처리할 필요가 없다는 것을 생각하면, x좌표 값들을 좌표압축해서 쓸 필요 없이, 그냥 쿼리들만 정렬해서 써도 될거 같은데? 한번 해볼까??? [TODO]
- sqrt방식..? 느릴거 같긴 한데.. 그래도 덜 복잡할거 같으니 한번 구현해보기나 할까
직선이 아닌 함수로의 확장
- 이 아이디어들을 직선이 아닌 좀더 일반적인 함수로 확장할수 있을까?
- 대상 함수셋을, 직선은 아니어도 되지만 두 함수는 최대 한 점에서만 만나는 조건을 만족한다고 바꿔보자.
- 그러면, 볼록껍질은 아니지만, 볼록껍질과 비슷한 특징을 갖는 그래프가 만들어진다. 특정 함수가 최솟값을 갖는 구간은 한개의 연속구간으로 제한된다. 그래서 볼록껍질처럼 각 함수가 최적이 되는 구간들을 구해두면 그 구간에 해당하는 함수에 대해서 값을 계산해줄 수 있었다.
- 직선일때는 어떻게 했더라 다시 정리해보자..
- 쿼리도 모노톤일 경우에는 함수들을 모노톤한 순서로 덱에 저장해놓기만 하면, 쿼리가 포함되는 구간을 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를 써버리는 것도 가능한 방법이다. 지금은 덱으로 구현해도 어차피 리니어타임에 처리는 불가능하기 때문에, 시간복잡도 상으로 손해보는것도 없다. (이론상 복잡도는 그렇고 실제 처리시간은 느릴수 있지만..)
분할 정복을 이용한 최적화와의 비교
- CHT를 쓸수 있는 함수는 선형 함수이다.
- 모노톤하게 정렬된 선형 함수들은 몽주 어레이로 만들수 있다.
- 몽주 어레이는 모노톤 매트릭스이고, 또 토털리 모노톤하니까 분할 정복을 이용한 최적화나 SMAWK로 풀수도 있다
- 하지만 분할 정복을 이용한 최적화를 쓰려면 점화식 형태이면 안된다. 다시 말해서 함수가 계속 추가되는 형태가 아니라, 함수가 미리 다 주어지고, 그 이후에 쿼리들이 들어오는 형태여야 한다.
- 또한 쿼리들이 전부 정수값이여야 한다.
- 요약하면..
- 함수가 미리 다 주어진 이후에, 정수값을 갖는 쿼리들만 들어온다면, CHT 대신 DnC최적화나 SMAWK를 사용해서 풀수도 있다.
최적화 방식 정리
- 여기저기서 주워들은 지식들을 적당히 정리해서 모아본건데 사실 정리가 깨끗하게 되지도 않고, 정확히는 오류도 좀 있다.
- 교점이 최대 1개인 함수들이 모노톤하게 정렬되어있으면 몽주가 된다.
- 아래쪽으로 갈수록, 오른쪽으로 갈수록 더 제너럴한 케이스이다. 각 방법들은 자기보다 왼쪽이나 위쪽에 있는 경우들에도 다 사용 가능하다는 뜻이다. 물론 사용처가 좁은 방식이 더 효율적으로 동작한다.
- 예를 들어 '직선'함수가 모노톤하게 추가되고 쿼리도 모노톤하게 들어올 경우에는, 언급한 O(n) CHT 외에도 이분탐색 CHT, 단조큐 최적화, LARSCH, Li Chao Tree 를 다 쓸수 있다는 뜻이다. 물론 가장 효율적인 것은 O(n) CHT.
| 직선 | 몽주(⊂토털리 모노톤) | 모노톤 | |
|---|---|---|---|
| 함수가 다 추가된 이후에 쿼리들이 모노톤하게 들어옴 | SMAWK | DnC 최적화 | |
| 함수가 모노톤하게 추가되고 쿼리도 모노톤하게 들어온다 | O(n) CHT | LARSCH | 단조 큐 최적화 |
| 함수가 모노톤하게 추가되고 쿼리는 아무렇게나 들어온다 | 이분탐색CHT | 단조 큐 최적화 + 이분탐색 | |
| 함수가 아무렇게나 추가되고 쿼리도 아무렇게나 들어온다 | Li chao tree |
- 언급 안한 방법들도 있다. 예를 들어 '함수가 아무렇게나 추가되고 쿼리는 모노톤하게 들어오면' Kinetic seg tree 도 사용 가능하다. 하지만 이 용도에서만 쓸때는 Li chao tree보다 우위가 없으므로 생략.
직선을 삭제도 해야할때?
- 롤백만 필요하다면..
- rollback 가능한 스택을 사용한다.
- 사실 이건 안해봤다.. 근데 덱을 쓰는 O(n)방식에서는 back쪽을 롤백할때, front쪽도 복원해줘야 하는 경우가 생길수 있을것 같다.. front쪽이 계속 줄어든다는 보장이 안되면 amortized O(n)을 만족시키지 못할거 같다..
- 이분탐색을 쓰는 방식에서도 잘 안될거 같은것이.. 사실 이경우는 스택이 그냥 스택이 아니라, 랜덤 액세스가 가능한 스택이어야 하는데.. 롤백가능한 스택은 링크드리스트로 만들어야 한다. 역시 안될거 같다
- rollback 가능한 li chao tree를 사용
- 이거는 가능하고 직접 해보기도 했다. 세그먼트 트리니까 라인 추가할때마다 O(logn)개의 노드만 업뎃된다. 롤백할때도 O(logn)개의 노드만 이전값으로 바꿔주면 된다.
- 퍼시스턴트 구조가 필요하면?
- Li Chao Tree를 dynamic seg tree로 만들었으면 PST를 만들듯이 persistent Li Chao Tree도 만들수 있겠지?
- 오프라인 쿼리이면, 오프라인 동적 연결성 문제를 풀듯이 분할정복을 써서 풀수도 있다고 한다.
- 임의의 직선을 삭제하려면?
- 이때는 kinetic seg tree를 쓸수 있는건가?? 좀더 찾아 보자..
그 외의 Li Chao Tree 활용?
- 직선이 아닌 선분을 추가하는 것도 가능한것 같다
- 코드포스 어떤 글에서 봤었던거 같은데.. 나중에 링크 추가하자.
- 볼수록 리차오 트리가 그냥 짱짱맨인것 같다
문제들
- DP가 아닌 문제
- DP문제
- ordered lines / ordered queries
- ordered lines / unordered queries
- unordered lines
ps/cht.txt · 마지막으로 수정됨: 2023/02/20 09:09 저자 teferi
토론