검색어의 복잡성?

Question

길이가 n 인 배열에 범위가 S={ (x1,y1) , (x2,y2) ,......(xk,yk) } 인 경우 집합 Q={ (l1,r1) , ......(li,yi) }에서 쿼리가 제공됩니다. 각 질의 (li, ri)는 집합 S에서 얼마나 많은 범위가이 범위 (li, ri) 사이에 속하는지를 의미합니다.
난 그냥 다음과 같은 일을 할 수 있는지 알고 싶어

1. Pre-computation in O(n) and then queries in O(1) 
    2 Pre-computation in O(nlogn) and then queries in O(logn) 

PS를 : 난 그냥 위의 두 점 솔루션을 싶지 않아, 난 내 자신에 대한 해결책을 마련하고자합니다.

Answer 1

여기 가야합니다. 이후 나는 예/아니오 대답을 줄 수 없기 때문에. 나는 너를 위해 신비를 망치지 않고 약간 정교 할 것이다. O에서 O에서

사전 계산 (n)은 다음 질의 (1)

는 세트 S의 범위가 정렬되도록 한 이후에는 (최종 요소 말할 수). 사전 계산없이 진행할 수 있습니다. 이것으로 우리는 전략을 정복하여 O(logn)의 질의 시간을 달성 할 수 있다고 믿습니다. 그러나 O(1)의 쿼리 시간을 얻는 것은 약간 멀리 보입니다. range trees 또는 kd-trees을 사용하더라도 가장 좋은 것은 O(log)입니다. 어쩌면 해시 테이블과 같은 보조 데이터 구조를 주어진 세트와 함께 사용하면 요리를 시도 할 수도 있지만 여전히 O(1)은 약간 야심적인 것으로 보입니다. 이 모든 것이 요구됩니다. 공간 요구 사항은 무엇입니까? O에서

O (nlogn)에서 미리 계산 한 후 쿼리 (logn)는

이 확실히 가능 보인다. 미리 정렬 된 것으로 가정하면 사전 계산을 위해 O(nlogn)이 필요하지 않을 수도 있습니다. Reg. 쿼리 시간, 집합 Q의 각 범위에 대해 O(logn) 시간이 걸립니다. 따라서 집합 Q의 k 범위의 경우 k * O(logn)이됩니다. 얼마나 크게 당신의 세트 Q를 기대합니까?