スプレー木
S を実行するコストは O ( m + n + ∑ j = 1 m log  ( | i j + 1 − i j | + 1 ) ) {\displaystyle O{\Bigl (}m+n+\sum _{j=1}^{m}\log(|i_{j+1}-i_{j}|+1){\Bigr )}} である。