Data structure for represent the cake in cake dividing problem?

Question

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

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?

Answer 1

Assumption :The cake is not 'cut' but 'marked' because cut result in partitions and hence there will be no overlaps.

An Interval tree can be used to solve this problem. Interval tree is a self-balancing BST. Each cake piece P(i,S) forms a node with range values i and i+S.
The structure of an Interval tree is given below

struct Interval
{
  float left;       \\ left - stores the leftmost value of the range
  float right;       \\right-stores the rightmost value of the range
 }
struct node
{
  Interval *interval;
  string ownerinfo;  \\ storing the name of the owner
   node *leftchild,*rightchild;  \\leftchild and rightchild are the pointers to the left subtree and right subtree of a node
 }

Each cake pieces P(i,S) are inserted into the tree takes O(logn) in worst case.

Queries :
1)The previous pieces inserted into the tree can be stored into a temporary variables. Checking whether the pieces overlap takes O(1) time.
2)Adding owner information takes O(logn) time in worst case. Traversing from a root node to the node representing the piece P(i,S) takes O(logn). The traverse is analogous to binary search.
3)The range or piece in which a point is contained can be find in O(logn) time .Since there is a possibility for the pieces to overlap a point i can be present in more than one cake pieces.Thus multiple answers are possible.
4)Similar to addition removal takes O(logn) time. Since removing owner information result in unowned cake pieces the nodes have to be removed and subtrees must altered. Deletion is similar to AVL trees.
5)The preorder traversal gives the owned pieces in the order.It takes O(n) time.