セグメント木

競技プログラミングでよく使われる「セグメント木」というデータ構造があります。 これは、配列データに対して2のべき乗区間ごとに「合計値」「最大値」など注目したい演算を適用しておき、任意の区間に対する演算結果を で取得できるものです。 セグメント木のイメージ 例えば、上記セグメント木は黄色で示した配列（8要素）が実データです。それに対して、注目している演算は「合計値」です。 セグメント木は区間に対する問い合わせ(Query)を で実現できて、要素に対する更新(Update)を で実現できます。そのため、区間に対する更新(Update)は の計算量を要します。 しかし、よく考えると区間に対する更新は…

第6回 アルゴリズム実技検定 (PAST) の問題 M - 等しい数 の解説です。 この記事では、範囲更新クエリ (RUQ) または平衡二分探索木を利用した解法を紹介します。 問題文はリンク先を参照してください。 atcoder.jp 解法の全体構成 まず、解法の全体構成は次のようになります。 同じ値が連続している部分を1つの区間と考える。クエリによる値の変更を何らかのデータ構造で管理することにより、各クエリに対して「どの値が何個増えたか (減ったか)」を求める。 なお、1回のクエリにより、複数の値 (区間) が影響を受ける可能性がある。 それぞれの値 (区間) に対する差分を全体の組合せ数に…

2020/12/21 更新 以下のリプライを頂きましたので, queue ではなく, 最後に参照された index のみ保持する実装に変更しました.operator[] を呼ぶたびに直前の operator[] を解決すると、履歴を stack から index 1 つに出来ると思いました— 熨斗袋 (@noshi91) 2020年11月4日 やりたいこと 1点更新区間和取得のセグメント木で 1 点更新を行う際, 多くは segtree.set_val(index, value) のように関数として呼んでいると思います. これが嫌なので, 1 点更新をsegtree[i] = xやsegtre…