3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Don't all the usual balanced tree (red-black, 2-3, etc.) satisfy this, with $O(\log N)$ even? $\endgroup$ – Gilles 'SO- stop being evil' Oct 30 '16 at 23:05
5
$\begingroup$

Chairman Tree is an alias of the data structure Functional Segment Tree. Its construction is fundamentally similar to a segment tree, only that it supports retroactive queries and modifications.

Every retroactive version is created by attaching new child nodes to the old parent node without modifying the original child node. Clearly, as the depth of a Chairman Tree should be no larger than $O(\log n)$, newly created nodes should be no more than $O(\log n)$ per operation. Therefore, total time complexity and memory complexity both equals to $O(n \log n)$.

Queries are performed by subtracting two versions and running a binary search, which might increase its time complexity to $O(n \log^2 n)$, should it contain modify operations. Note that modify operations are only available while operations can be performed offline.

Here's a paper which might help you understand functional data structures better: Purely Functional Data Structures


For the reason why it is called a Chairman Tree, let me take some time to explain. This data structure is first widely introduced in China by an OI participant @fotile96, who had been unable to code a Partition Tree which also performs retroactive operations, had to invent another data structure that was called a Functional Segment Tree. However, the phonetic letters of @fotile96 was the same as the former president of People's Republic of China, other participants happened to call him Chairman, which induced the name of Chairman Tree.

The inventor himself showed reluctance to the name, however.

Here's a link in Chinese which demonstrated the question: https://www.zhihu.com/question/31133885

$\endgroup$
5
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.