[일반] Lca할때 Hld?희소테이블?

[익명(106.101)]

Hld가 더 빠른걸로 알고있는데
희소테이블로 tle뜨는걸 hld면 통과될 정도임?

[익명(118.235)]

그런 괴상한 시간 제한을 가진 문제면 구축이 중요한 게 아니고 쿼리당 O(1) 하는 거 구현해야 함

[익명(106.101)]

ㅇㅇㅇ그니까 이상해서 그럼 둘중 하나만 알아도되는거 아닌가

[익명(14.45)]

hld는 빌드 O(n) 쿼리 O(log n) 스파스는 빌드 O(n log n) 쿼리 O(1)이라 n보다 쿼리 개수가 훨씬 크면 스파스 써야됨

[익명(14.45)]

그 외의 상황에선 거의 항상 hld가 우위

[익명(49.168)]

O(n)하고 O(nlogn) 구분짓는 문제를 거의 못 봄 여우 국수라고 n범위 500만이고 시간제한 0.5초인 문제가 있긴 한데 그건 특수케이스긴 함 그냥 아무거나 써도 될 듯?