in Others edited by
38 views
0 votes
0 votes

Let $P$ be a set of $n$ real numbers. For any two real numbers $a$ and $b$ $(a<b),$ define $$ R(a, b)=|\{x \in P \mid a \leq x \leq b\}| . $$

  1. Design a suitable data structure $\mathcal{D}$ to store $P$ such that given $a, b$ $(a<b)$ as inputs, you can find $R(a, b)$ in time $O(\log n)$. Analyze the time required to construct your data structure $\mathcal{D}$.
  2. Justify that $O(\log n)$ time is sufficient for reporting $R(a, b)$ using your data structure $\mathcal{D}$.
in Others edited by

Please log in or register to answer this question.

Related questions