列の連結/全要素列挙をする永続データ構造

某に載せるほどか...? 載せることにしたらこっちは消えます
以下の操作を実現する永続データ構造が存在する

• 
  単一の要素 からなる列を作成する
  時間/空間計算量
  
• 
  列 を連結した列を作成する
  時間/空間計算量
  
• 
  列 の全要素を順に列挙する
  時間計算量
  

アルゴリズム

各要素を葉に持つ二分木 (非平衡) を永続化すればよい。
は を左子、 を右子に持つノードを作る。
は DFS で木を走査する。