セグメント木

永続セグメント木

データ構造 永続データ構造 セグメント木 モノイド 区間クエリ

1. 概要 通常のセグメント木は，更新を行うたびに古い状態を破棄し，常に最新のバージョンだけを保持する構造になっています．それに対して 永続セグメント木 は，過去のすべてのバージョンに対してアクセスや更新が可能なセグメント木です． 永続セグメント…

Wavelet Matrix（発展）

データ構造 区間クエリ 矩形クエリ Wavelet Matrix Binary Trie セグメント木 Fenwick 木 座標圧縮

1. 概要 Wavelet Matrix の基礎的な理解や実装方法については， Wavelet Matrix（基礎） で解説しました． 本記事では改めて，Wavelet Matrix を使うとどのような処理をできるのかについて，具体的な例をいくつか確認します． なおほとんどの例について，Wav…