https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf に$m, n \ (m \le n)$要素のTreapのunionで期待計算量が${O}(m \log (n/m))$であるものが紹介されている。これを使うと次のことができる:
1要素のTreapが$N$個与えられたとし、これらのTreapに任意の順番で$N-1$回unionを適用して$N$要素のTreapを作るとする。この時、全体の期待計算量は${O}(N \log N)$である。
これはマージテクと同じように理解できる:
まず、定数$B$が存在して$m, n\ (m \le n)$要素のTreapのunionの期待計算量は$B m \log (n/m)$以下である。
求める計算量を$T(N)$とする。$C>0$が存在して$N$未満の整数$x$については$T(x) \le C x \log x$が成り立っていると仮定する。このとき、$T(N) \le C N\log N$であることを示せばよい。この際、$C \ge B$としてよい。
$$ T(N) \le \max_{m+n = N} \bigl (Bm \log \frac{n}{m}+ T(m) + T(n) \bigr) $$であるから、任意の分割$N = m+n \ (0 < m \le n)$について$Bm \log (n/m) + T(m) + T(n) \le C N \log N$が成り立つことを示せばよい。実際、次のように示せる:
$$ \begin{aligned}& Bm \log \frac{n}{m}+ T(m) + T(n) \\ \le \ & B m \log \frac{n}{m} + Cm\log m + C n \log n \\ \le \ & C \bigl (m\log\frac{n}{m} + m\log m + n \log n \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n \log \frac{n}{m}m \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n\log \frac{n}{m} + n \log m \bigr ) \\ = \ & C \bigl ((m+n) \log \frac{n}{m} + (m+n)\log m \bigr ) \\ = \ & C \bigl (N\log \frac{n}{m} + N \log m \bigr) \\ = \ & C(N\log n - N\log m+ N \log m) \\ = \ & CN\log n \\ \le \ & CN\log N \\ \end{aligned} $$（$\log 1 = 0$ 問題があるのであまり正確でない。）
