【まとめ】セグメント木・遅延評価セグメント木

セグメント木

セグメント木は、区間更新・区間上の最小値や和などをO(logn)で求めることができるデータ構造です。

セグメント木を理解するために役立つリソース

かつっぱさんの動画です。説明が丁寧なのでわかりやすいです。

part1では、セグメント木の雰囲気が説明されています。
【木マスター養成講座】4-1. Segment木ってなに〜？導入編【競プロかつっぱ】

part2では、RSQを非再帰で実装するところまで説明されています。
【木マスター養成講座】4-2. Segment木ってなに〜？なんかうまく区間取ってくる編【競プロかつっぱ】

part3では、RAQ(区間加算)を実装します。
【木マスター養成講座】4-3. Segment木ってなに〜？RAQ編【競プロかつっぱ】

part4では、RMQを再帰で実装します。
【木マスター養成講座】4-4. Segment木ってなに〜？再帰で区間取ってくる編【競プロかつっぱ】

その他実装に役立つブログ・サイト

セグメント木をソラで書きたいあなたに
セグメント木を徹底解説！0から遅延評価やモノイドまで

セグメント木を使用する問題

AOJのコースの一つです。セグメント木の基本を理解するのにうってつけの問題です。
AOJ/データ構造とクエリ処理#区間クエリ

↓このコースの問題に関する自分の記事
【AOJ】Range Minimum Query (RMQ)
【AOJ】Range Sum Query (RSQ)
【AOJ】Range Add Query (RAQ)
【AOJ】Range Update Query (RUQ)

簡単。やるだけ。
ABC185 - F - Range Xor Query

遅延評価セグメント木

遅延評価によって、区間更新・区間クエリを同時にO(logn)でできるようになったデータ構造です。

遅延評価セグメント木を理解するのに役立つリソース

遅延評価の仕組みについても解説されていてわかりやすいです。
遅延評価セグメント木をソラで書きたいあなたに

普通のセグメント木の方でも紹介しましたが、こちらもわかりやすいです。
セグメント木を徹底解説！0から遅延評価やモノイドまで

遅延評価セグメント木を使用する問題

セグメント木の方で紹介したのと同じコースです。&がついている問題は遅延評価セグメント木を使って解けます。
AOJ/データ構造とクエリ処理#区間クエリ

↓このコースに関する自分の記事
【AOJ】RSQ and RAQ
【AOJ】 RMQ and RUQ
【AOJ】RMQ and RAQ
【AOJ】RSQ and RUQ