title: Is it possible to query number of distinct integers in a range in O(lg N)?
body: <p>I have read through some tutorials about two common data structure which can achieve range update and query in O(lg N): <a href="https://en.wikipedia.org/wiki/Segment_tree" rel="noreferrer">Segment tree</a> and <a href="https://en.wikipedia.org/wiki/Fenwick_tree" rel="noreferrer">Binary Indexed Tree</a> (BIT / Fenwick Tree).</p>
  <p>Most of the examples I have found is about some associative and commutative operation like &quot;Sum of integers in a range&quot;, &quot;XOR integers in a range&quot;, etc.</p>
  <p>I wonder if these two data structures (or any other data structures / algorithm, please propose) can achieve the below query in O(lg N)? (If no, how about O(sqrt N))</p>
  <p><em><strong>Given an array of integer A, query the number of distinct integer in a range [l,r]</strong></em></p>
  <p>PS: Assuming the number of available integer is ~ 10^5, so  <code>used[color] = true</code> or bitmask is not possible</p>
  <p>For example: A = [1,2,3,2,4,3,1],  query([2,5]) = 3, where the range index is 0-based.</p>