spoj 16793. Statistics Applied | EC_ESTA

All we have to do is to construct a perfectly balanced binary tree so that we can always get the median in O(1). and each insertion at most takes O(log(n)), but it’s rather too complicated to construct a perfectly balanced binary search tree, so we keep 2 Queues as the two branches of this perfectly balanced binary tree.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s