sugarknri https://blog.hatena.ne.jp/sugarknri/ メモ https://sugarknri.hatenablog.com/ テクニック この記事では遅延セグメント木の「気持ち」を説明します。 通常のセグメント木に関する知識を前提とします。 アルゴリズムの説明のみであり、実装については一切説明していません。 基本的には以下のサイトの記述を、自分好みにリライトしたものです。 beet-aizu.hatenablog.com ○遅延セグメント木とは半群 作用素モノイドの部分モノイド の写像 があり、次の(1)～(3)の条件を満たすとする。 (1) の演算、作用素の適用、作用素の合成はいずれもで行える (2) はにもにも依らずで計算できる (3) *1このとき上の長さの列に対する2種類のクエリ(i)(ii)を遅延セグメント木によってで… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsugarknri.hatenablog.com%2Fentry%2F2018%2F04%2F16%2F123016" title="遅延セグメント木 - メモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=O%28%20%28%5Clog%20N%29%5E2%29 Hatena Blog https://hatena.blog 2018-04-16 12:30:16 rich https://sugarknri.hatenablog.com/entry/2018/04/16/123016 1.0 100%