XGG Blog
Order-maintenance problem is the maintenance of a list when considering the simplest case. The list supports the following operations:
This problem can be solved by applying some kinds of self-balanced binary search trees, and the time complexity is for deletion and querying of order.
The Simple Structure
They used circular linked list for maintaining the list, every item . Assuming the length of the list is . The only problem remains is how to maintain the label.
Denote the label of , the procedure of insertion is:
The loop in the first step always terminates because .
The following is an implementation of the structure, bi-directional linked list is used for deletion:
const int M = 1e8;struct Node{int value;int label;Node* prev;Node* next;};Node* createList(){Node *head = new Node();head->label = M;head->prev = head;head->next = head;return head;}void destroyList(Node* head){Node* oldHead = head;do{Node* next = head->next;delete head;head = next;}while (head != oldHead);}// Insert(x, y)void insertNode(Node* x, Node* y){int v0 = x->label % M, w;Node *spy = x->next;int j = 1;while (true){w = (spy->label – v0) % M;if (w <= 0){w += M;}if (w > j * j){break;}spy = spy->next;++j;}Node *laborer = x->next;int k = 1;while (laborer != spy){laborer->label = ((long long)w * k / j + v0) % M;laborer = laborer->next;++k;}y->label = (v0 + x->next->label) >> 1;y->prev = x;y->next = x->next;x->next->prev = y;x->next = y;}// Delete(x)void deleteNode(Node* x){x->prev->next = x->next;x->next->prev = x->prev;}// Order(x, y)bool getOrder(Node* x, Node* y){return x->label < y->label;}
Deletion and querying is amortized time complexity for all operations.
，人生就是一次充满未知的旅行，在乎的是沿途的风景，
