はてなブックマーク

競技プログラミングに慣れ親しんでいる方なら、セグメント木というデータ構造について、一度は聞いたことがあるでしょう。この記事は、セグメント木の構造を理解する必要はないが、使い方を知っておきたいという方のために書かれています。 この記事では、まずセグメント木について紹介し、それからセグメント木を実際に使う際の技法について紹介します。 セグメント木とは セグメント木は、固定長配列にいくつかの操作を加えたデータ構造です。セグメント木は、基本的には以下の操作を時間計算量 O(\log n) ですることができます。 i 番目の要素に x を代入 i 番目の要素を取得 l 番目の要素から r 番目の要素のモノイド積[1]を計算 ここで、モノイドを知らない方もいるかもしれませんので、モノイドについて紹介します。 モノイド モノイドは、実数や複素数の足し算や掛け算、文字列の連結といった、集合とその演算をまと