区間 \([a, b)\) を赤黒木で管理する.

区間 \([a, b)\) を挿入する際には, \([a, b)\) の直前の区間を求め, 直前の区間と重なっていればその区間を使う.

さらに区間 \([a, b)\) より後ろの区間を調べ, 重なっていれば後ろの区間は消していく.