hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 累積和・imos法 累積和 累積の和をとっておくと、区間の総和がO(1)で取得できる 参考 累積和は、先頭からの和だけでなく、先頭からの積・先頭からのgcdも可能である。交換則も必要ないので、行列に対しての計算も可能である 【テク1】ある要素以外の最大とかを求めたいときは、先頭からと後尾からの累積和を取る典型がある 2次元に拡張することもできる imos法 一定区間にある数を足すクエリを仕込みO(1),後処理O(N)で行う方法 本家解説 普通は0次1次元であるが、高次高次元に拡張できる(らしい) なんかすごい記事が爆誕してた 問題 累積和 1次元累積和 yukicoder No.607 開通7… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F07%2F04%2F020117" title="競技プログラミングにおけるimos法・累積和問題まとめ - はまやんはまやんはまやん" 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 2017-07-04 02:01:17 rich https://blog.hamayanhamayan.com/entry/2017/07/04/020117 1.0 100%