null_mn https://blog.hatena.ne.jp/null_mn/ メモ帳 https://null-mn.hatenablog.com/ たまに見る割にまとまった記事がない気がしたので 区間に等差数列を作用させる遅延セグメントツリーとは 長さ の数列 に対し次のような操作が全て で行えます。 をそれぞれ で更新する。 の最小値/最大値/総和を取得する。 後程述べますが、少し変えると区間等差数列加算・区間和も扱えます。 仕組み 次のような更新を目標にします。 をそれぞれ で更新する。 これはセグ木のノードに最小値、最大値、総和、左端/右端のindexを持たせることで実現できます。ノードのマージはそれぞれのminやmaxをそのまま取ればよいです。作用素の作用については、区間 を で更新するとき、 なら左端が新しい最小値となり、右端が… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnull-mn.hatenablog.com%2Fentry%2F2021%2F08%2F22%2F064325" title="区間に等差数列を作用させる遅延セグメントツリー - メモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-08-22 06:43:25 rich https://null-mn.hatenablog.com/entry/2021/08/22/064325 1.0 100%