1. Ji Driver segment tree
   
2. Gomory Hu trees
   
3. Maybe some math serious topic.

SGT Beats use of segment tree(mentioned here).

Also, I think your article should mention that Li-chao can easily be extended for parabolic functions much easily(useful for problem KILLER)

(O(n), O(1)) RMQ algorithm by Fischer and Heun (link).

adamant I'll look into it. Looks like all images are broken on e-maxx-eng.

Site works for me

will there be any operation that only li-chao segement tree could handle?

Just as you describe, we can use binary search trees(ex. implicit treaps) to replace any segment tree with only n nodes. But with the high constant they are unlikely to be any faster/have less memory usage than a segment tree. (Also atleast for me, a segment tree is much faster/easier to code.)

I actually can't see the reason for this exact comment being downvoted. I can see reasoning behind downvoting most of the comments from this account, as most of them are rude or unpleasant in some way. But here i make 3 points and each of which seems ok:

1. I mentioned about a mistake in an article and asked to extend it. You want exact test case where random linking performs badly? It's just easy-peasy: let's link 1 to 2, then 2 to 3, ... 3 to n. Then, expected value of tree height is n / 2 which is easy to prove by induction. I also mentioned, how priorities are chosen in the original paper, which corrects the original articl on cp-algorithm. This seems more than OK to me.

2. I asked a cool coder whether he knows a test where upper bound for DSU with path compression only is achieved. I googled some information on this topic, but failed, so it is at least not too easy to find it and it is good to ask this question in public, in case there will be other people interested in this topic.

3. Finally, i mentioned a technique, which may make your life a bit easier and your DSU a little faster and provided a link to an article.

I do not see why this comment was so heavily downvoted. I pointed to a mistake in an article and proposed some ways to improve it. Even if at won`t, i am strongly convinced that a comment upwards has educational value itself and is useful for the cf community.

Yes, this is one of the most common mistakes with randomized linking. Here is a 3 year old discussion about this that's work reading. To summarize the discussion:

• There afaik is no proof that shows $$$O(n\ \alpha (n))$$$ runtime for randomized linking by flipping a fair coin, i.e. by if(rand()%2). In fact, a benchmark from the linked page suggest otherwise, namely that the runtime is close to $$$\Theta(n \log n)$$$.
• The paper on randomized linking talks about giving every node a random weight and always linking the node with lower weight to the one with higher weight. This is equivalent to flipping a biased coin with weights equal to the sizes of the individual trees, which makes it closely related to union by size.
• The paper also conjectures that randomized linking by flipping a fair coin needs $$$\Omega\left(n \frac{\log n}{\log \log n}\right)$$$ time w.h.p.

To answer your question on worst-case inputs for path compression:

• In the paper Worst-Case Analysis of Set Union Algorithms, it is shown that if we start with a binomial tree of height $$$h = \lg(\frac{n}{2})$$$ (so with $$$2^h = \frac{n}{2}$$$ nodes), link it to a single node and then do a find operation on a deepest leaf, we end up with our binomial tree of height $$$h$$$ (and a node attached to the root of it). This allows us to repeat these steps $$$\frac{n}{2}$$$ times (using the remaining $$$\frac{n}{2}$$$ nodes). Each find operation takes $$$\Theta(h) = \Theta(\log n)$$$ time, resulting in $$$\Theta(n \log n)$$$ total runtime.
• There are some nice pictures of this in the paper and they make understanding the behavior of binomial trees under path compression a lot easier.

• I haven't thought too much about this, but if we allow later queries to depend on the answer to earlier find queries (i.e. something like an iterative union-find problem), then the following might show a $$$\Omega\left(n \frac{\log n}{\log \log n}\right)$$$ bound for randomized linking by flipping a fair coin:

  1. This construction is based on the case $$$m = n \log n$$$ from the paper, where $$$j = \log n$$$ and $$$i \in \Theta\left(\frac{\log n}{\log \log n}\right)$$$.
  2. In the paper, they fix a parameter $$$j$$$ and then for $$$k = i \cdot j$$$ define trees $$$T_k$$$ on which we can do $$$1$$$ unite operation and $$$j$$$ find operations so that we get back $$$T_k$$$ with an additional (useless) leaf and so that each find operation takes $$$\Theta(i)$$$ time. $$$T_k$$$ contains at most $$$(j+1)^{i-1}$$$ nodes, so picking $$$i = \log_j(n) - \Theta(1)$$$ makes $$$T_k$$$ contain at most $$$\frac{n}{2}$$$ nodes.
  3. Similar to the paper, we fix a parameter $$$j$$$. Our goal is to define trees $$$S_k$$$ which can be built with randomized unite operations. Moreover, we want $$$S_k$$$ to contain a copy of $$$T_k$$$.
  4. We define $$$S_k$$$ recursively. If $$$k \leq j$$$, then $$$S_k$$$ consists of a single node. Otherwise it consist of a copy of $$$S_{k-j}$$$ to the root of which we attach $$$j-1$$$ copies of $$$S_{k-j}$$$.
  5. We can build $$$S_k$$$ recursively by building $$$j$$$ copies of $$$S_{k-j}$$$, connecting them with $$$j-1$$$ unite operations. Finally, we do a a find operation on one of the $$$S_{k-j}$$$ to find the root of the $$$S_k$$$.
  6. If you compare this construction to figure $$$11.a$$$ from the paper, it is clear that $$$S_k$$$ contains $$$T_k$$$. To figure out where to query, we need an explicit embedding from $$$T_k$$$ to $$$S_k$$$. For $$$k \leq j$$$, this is the identity, for $$$k > j$$$, we can compute such an embedding out of the embedding of the $$$T_{k-j}$$$ in the recursively built $$$S_{k-j}$$$. (Note that an embedding of $$$T_{k-j}$$$ into $$$S_{k-j}$$$ also gives us one from $$$T_{k-j-l}$$$ into $$$S_{k-j}$$$ for any $$$l > 0$$$.
  7. With this construction, $$$T_k$$$ contains at most $$$(j+1)^{i}$$$ nodes, so if we pick $$$i = \log_j(n) - \Theta(1)$$$ we use at most $$$\frac{n}{2}$$$ nodes.
  8. Once we constructed $$$S_k$$$, we only keep the copy of $$$T_k$$$ contained in it and forget all the other nodes from $$$S_k$$$.
  9. In the paper, it show that we can perform one unite query followed by $$$j$$$ find queries so that we get $$$T_k$$$ back and each find query needs $$$\Theta(i)$$$ time. Let's call such a batch of queries a phase. To deal with the fair coin flips, we do the single unite by "trying $$$2 \log_2(n)$$$ times". Let $$$a$$$ denote the current root, then repeat the following steps $$$2 \log_2(n)$$$ times: Take a single node tree $$$b$$$, unite $$$a$$$ with $$$b$$$ and set $$$a$$$ to $$$\operatorname{find}(a)$$$. This does not change the shape of the $$$T_k$$$ and with probability $$$\frac{1}{2}$$$, it add an upward edge from the root of the $$$T_k$$$. The probability of this not happening in any of the steps is $$$\frac{1}{n^2}$$$.
  10. Set $$$j = \log_2(n)$$$, $$$i$$$ as above so that $$$S_k$$$ contains at most $$$\frac{n}{2}$$$ nodes. With the remaining $$$\frac{n}{2}$$$ nodes, we can do $$$\frac{n}{4 \log_2(n)}$$$ phases. In every phase, we do $$$\Theta(j)$$$ queries needing $$$\Theta(i)$$$ time each, so a phase needs $$$\Theta(j i) = \Theta\left(\frac{(\log n)^2}{\log \log n}\right)$$$ time. As there are $$$\Theta\left(\frac{n}{\log n}\right)$$$ phases in total, we get a runtime of $$$\Theta\left(n \frac{\log n}{\log \log n}\right)$$$.
  11. The probability of failure of one phase is $$$\frac{1}{n^2}$$$, so by union bound, the the probability of failing at least once is at most $$$\frac{1}{n}$$$, so with high probability, we indeed get the desired lower bound.

Let me know it you have questions regarding the proof or if you find a mistake it it. There are probably some typos in the LaTeX parts.