Cheap and Secure Web Hosting Provider : See Now

[Solved]: What is the "Chairman Tree"?

, , No Comments
Problem Detail: 

My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs queries and updates in ${O(log^2N)}.$ What information is there on this tree, and does it go by a different, more popular name?

To be clear, any data structure that fulfills the above will be considered as a correct answer. The first one will be marked correct. If there is a link, that would be the best.

Asked By : Max Li

Answered By : Ivan Smirnov

I've been doing competitive programming for several years at a very high level and haven't ever heard of a Chairman tree. Though I still can tell you how to make any data structure persistent. In case of BSTs and segment trees it even doesn't increase the running time (asymptotically, of course; you can notice some slowdown in practice).

First, let's consider a basic segment tree. I'll write C++-ish code because such trees, when made persistent, are most conveniently interpreted with pointers. For sake of simplicity I'll describe a (rather stupid) tree with two simple operations: assign a number to a position $i$ and get a number on a position $i$.

struct node {     int l, r;     node *L, *R;     int value;      void put(int i, int x) {         if (l == r) value = x;         else if (i <= L->r) L->put(i, value);         else R->put(i, value);     }      void get(int i) {         if (l == r) return x;         else if (i <= L->r) return L->get(i);         else return R->get(i);     } } 

For those who are not familiar with notation (though it should be clear from the code): a node represents a segment $[l, r]$ of an array. When $l = r$ the node is a single element, else it has two children, $L$ and $R$, having ranges, respectively, $[l, (l+r)/2]$ and $[(l+r)/2+1, r]$.

When you put a value to a tree, you modify it. But we may notice that each modification touches only $O(\log n)$ nodes of a tree, so instead of modifying existing nodes we may copy them and apply updates only to the new vertex.

Here is the outline: whenever the function wants to modify a node, it makes a copy, modifies a copy and returns the copy back to the caller (because the caller wants to update himself too). In this example only put must be modified, and here we go:

node* put(int i, int x) {     node *t = this->makeCopy();      if (l == r) t->value = x;     else if (i <= L->r) t->L = t->L->put(i, value);     else t->R = t->R->put(i, value);      return t; } 

Voi-la! Now we have got a fully-functional persistent array which takes $O(\log n)$ time and space per operation. You only have to store pointers to the roots of versions you need, and as long as the pointer is saved, it will stay untouched. Forever.

The very same technique may be applied to any kind of a segment tree, giving no overhead in time (because segment tree queries are already $O(\log n)$. More, you can use this approach with BST's. The most reasonable choice of a structure to make persistent is a Treap, mostly because it does not require storing pointers to parents. It might be hard to understand which values exactly one should clone while splitting and merging, but it is done in several minutes with pencil and paper.

Now a bonus and a tiny warning. First, you can make any data structure persistent: just implement it using persistent arrays :) If the structure itself is not tree-ish, this will cost you a logarithmic increase in time, of course. Second, this technique cannot be applied to any DS which running time is amortized, so be careful with persistent splay tree.

Hope this helps, and don't hesitate to ask something in comments!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65312

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback