Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

GFG article with interesting time complexity (merging std::set in O(1))

Revision en3, by Everule, 2020-08-31 20:06:23

Some newbie messaged me with asking for help on this article https://www.geeksforgeeks.org/queries-for-number-of-distinct-elements-in-a-subarray-set-2/.

Can someone explain why time complexity is O(log n) and not O(n)?

Please read it once before downvoting. It is an advanced data structure, that is not well known.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Everule 2020-08-31 20:06:23 27
en2 English Everule 2020-08-31 19:48:45 30
en1 English Everule 2020-08-31 19:44:36 355 Initial revision (published)