[일반] LCA 오일러 경로 + 희소배열로 구하는거 말고 간단한 방법 혹시있음??

[펜져(penzer27)]

만들 때 경로탐색에 O(N)
희소배열 구성에(NlogN)
검색에 O(logN) 이게 최선입니까??

[익명(122.39)]

난 hld 더 선호하긴함 근데 둘다 구현 난도는 비슷한거같은데

[펜져(penzer27)]

오우 자료 찾아보고 왔는데 HLD가 더 직관적으로 간단한 느낌인데?! 감사감사!!! 공간복잡도도 덜 먹고

[익명(39.7)]

nlogn이하로 복잡도를 줄이는건 불가능할걸? 방법의 차이지

[펜져(penzer27)]

HLD O(N) 아님?? 순회에 O(N) 검색에 O(logN) 뭘 놓치고 있나

[익명(58.237)]

LCA는 구간 최솟값 쿼리(RMQ)로 환원할 수 있고 세그로 LCA 구하는 게 그런 방식인데 RMQ는 O(N) 전처리에 amortized O(1)에 풀 수 있는 방법이 존재함. 그래서 전처리 O(N)에 구하는데에 amortized O(1)으로 구할 수 있긴 함. 사실 이거보단 전처리 O(NlogN) 구하는데에 O(1)의 방법이 더 실전적일듯 RMQ로 환원하고 스파스만 잘 쓰면 됨

[펜져(penzer27)]

선생님 상세한 답변 감사합니다 ㄷㄷ RMQ를 O(N) 전처리 만드는 방법의 존재, 그리고 나는 지금 검색시 O(logN)이라고 생각하고 있는데 뭔가 O(1) 짜리 방법이 있는듯?? 찾아봅니다.;)

[익명(210.217)]

https://cp-algorithms.com/graph/lca_farachcoltonbender.html#algorithm
윗댓에나온
O(N) 전처리 O(1) 쿼리 LCA인데 개인적으로는 오일러 스파스가 최선이라생각함

[펜져(penzer27)]

어제 읽다가 자서 일어나서 마저 봤음. 기존 RMQ가 block_size 1이라고 생각하면 되겠네! block_size를 늘리면 전처리 할 때 이득이고, 검색 시에도 min(block_l, block_inter, block_r) 로 O(1)에 구성 할 수 있다는 거인듯 ㄷㄷ ;; 뭔가 외계인이 생각할만한 것 까지는 아닌데 구현 난이도 숨막힌다 ㄷㄷ

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[펜져(penzer27)]

ㄱㅅㄱㅅ 흥미롭게 읽었음

[익명(112.187)]

고인물 총출동하는거봐 난 스파스밖에 모르는데

[펜져(penzer27)]