Got inspiration while reading history book. Inspired by: [China, the cake of kings and emperors, Le Petit Journal 1898][1]

**Background:** 

> After the Second Opium War, United Kingdom(UK), France, Russia, Germany and Japan have a meeting to dividing China the cake. 

The cake have fixed size but can be break down into many small pieces with different size. To make it is easier to divide, the cake start point is denoted as 0 and end point is denoted as 1, then a piece of cake can be denoted as P(i, S) with i is the position of that piece in the cake and S is the size of that piece 
 
> Initially, UK grab half of the cake, the rest grab few pieces at different location and some pieces of the cake no one want it. Then France noticed that UK take too much and start to complain. UK then split that big piece in to many smaller pieces and give other country some pieces among them, of course there are also pieces no one want among them, then UK take another not so large piece somewhere else. But this piece is overlapped with one piece Germany have, so Germany have no choice but to give up on their piece and pick somewhere else. After few more debates everything has become a mess and hard to track which piece belong to whom. UK then make a call to his brother America and ask him which data structure can be used to represent this cake. 

**Problem:**
To avoided starting World War over China the cake, America must think of a data structure to store <Country - Cake pieces> information which as efficient as possible to perform these following operation:

 1. Given P(i, S), find out the previous piece and the next piece and check if it is overlapped or not
 2. Given P(i, S), add owner information
 3. Given i, find out the owner of cake piece contain it
 4. Given P(i, S), remove owner information
 5. From the start position to the end position of the cake, list all owned cake pieces in order 

Data structure do not need to store unowned cake pieces

**Question:**

 1. If you are America, what data structure would you suggest if all operation have same frequency of usage and show complexity of each required operation to prove your opinion?
 2. Given that operation 2 and 5 is used the most, what data structure would you used?


  [1]: https://commons.wikimedia.org/wiki/File:China,_the_cake_of_kings_and_emperors,_Le_Petit_Journal_1898.jpg