Segment Tree を少し速くする - Fixstars Tech Blog /proc/cpuinfoこのブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。 Segment Treeと呼ばれるデータ構造があります。 プログラミングコンテストでも解法の一部として使われることが多いため、よくコンテストに参加するような人だとコピペで使えるように準備しているということも多いのではないかと思います。 このデータ構造を使うと、1次元の数列に対する以下の操作が $O(\log n)$ の時間計算量で可能となります。 query(l, r): $a_{l}\ \textrm{op}\ a_{l+1}\ \textrm{op}\ \cdots\ \textrm{op}\ a_{r-2}\ \textrm{op}\ a_{r-1}$ を求める update(i, x): $a_{i}$ に $x$ を代入する たとえば、最初に数列 $a = [ 0, 1, 2
