定期宣伝

弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．

Spir | Smart scheduling calendar

この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．

区間を覆う完全二分木

以下のような長さ $N$ が2冪の区間を覆う完全二分木を考える． この二分木自体を指してセグメント木と呼ぶ場合も（多分）ある．

![$0,16)$ の区間を覆う完全二分木 奇数を青・偶数を赤で色分けしている

$[0,16)$ の区間を覆う完全二分木 奇数を青・偶数を赤で色分けしている

• もう少し厳密な定義

まずこの木の性質を確認する． 以下ではしばしば木の頂点とそれに対応する区間を同一視する．

事実

• 木の高さは $O(\log N)$．
• 特に区間上の任意の点 $i\in [0,N)$ について $i$ をカバーする頂点は $O(\log N)$ 個．
• ある高さで境界線が存在するなら，それより下の高さでも同じ位置に境界線が存在．
• 赤青の順で頂点が横に隣接していることと，二頂点が兄弟であることは同値．
• 青赤の順で頂点が横に隣接していることと，真上にも境界線があることは同値．

定理1

任意の区間 $[l,r)$ は $O(\log N)$ 個の頂点の非交和で表せる．

• 例

証明の概略