### Amer_Oniza10's blog

By Amer_Oniza10, history, 2 months ago,

Hi ... Is there a way to find the number of different integers within a range of log(n) complexity?

• -21

 » 2 months ago, # |   -6 use a map may be bro
•  » » 2 months ago, # ^ |   0 Maybe.. but I don't think so
•  » » 2 months ago, # ^ |   0 its so slow...
 » 2 months ago, # |   -15 Use a segment tree. Whenever you add a new element set its value as 1. When you want to know how many values in range [l,r] you can get the sum of the range (l,r)
•  » » 2 months ago, # ^ |   0 Thanks
•  » » » 2 months ago, # ^ |   0 Wait, what do you mean by range? Is it a subarray or a range of numbers?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 hey we can use map also ?
•  » » » 2 months ago, # ^ |   0 You can use, but that way is be slower than segment tree. You can also use set. But it is also slow...
 » 2 months ago, # |   0 Hint: Offline+Fenwick.
 » 2 months ago, # |   0
 » 2 months ago, # |   +8 make array nxt[i] that means index of number that equal a[i] if there are no such set INFthen for answer u need to find number of nxt[i] that less r on range l<=i<=ruse Segment tree
•  » » 2 months ago, # ^ |   0 He wants in O(logn) complexity. Your's is O(log^2n).
 » 2 months ago, # |   +5 Hello freind you can simply use 1 pointer technique to solve this. Move your lazy ass pointer finger and count whatever you want in the segment
 » 2 months ago, # |   0 Persistent segment tree if you need online, else Fenwick and offline