遅延セグメント木（Lazy Segment Tree）の使い方を解説します。 セグメント木とは セグメント木（以下、セグ木）とは、二分木を作り、各ノード（頂点）に区間の情報を与えることで、区間クエリに で答えることができるデータ構造です。セグ木にはモノイドが乗ります。モノイドとは、以下の性質を満たす「集合Sと二項演算Fの組」です。 1. Fについて閉じている Sの元と元でFをしたとき、その返り値がSの元である。 2. 結合則を満たす 例えば、Sの元s1、s2、s3について、F(F(s1, s2), s3) == F(s1, F(s2, s3))が成り立つ。 つまり、順番はそのままにしてどこから…
