38 views

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}$.