こんにちは, kagamiz(@kagamiz) です! この記事は, Competitive Programming Advent Calendar Div2012 18日目の記事として書かれました. この記事では, ぼくが気に入っているデータ構造であるセグメント木について, 説明と問題演習・問題紹介を交えながら紹介していきたいと思います. RMQ(Range Minimum Query)を処理するセグメント木はわかるけど, そこから応用するのが難しい...という方向けに書いていきます. 説明の章の先頭には, 水色の★もしくは黄色の★をつけています. ★は「プログラミングコンテストチャレンジブック」などでも触れられている事項で, ★はそうでない事項を指します. 演習問題の先頭には★マークをつけていますが, ★は基本的な問題, ★はやや難しい問題として示しています. 概要についてですが,