atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ データ構造 区間クエリ Wavelet Matrix Binary Trie 解説動画はこちらです． 1. 概要 本記事では，Wavelet Matrix というデータ構造について解説します。 Wavelet Matrix とは大雑把に言えば，静的な非負整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ に対して，クエリ $(L,R)$ が与えられるたびに，「多重集合 $\lbrace A _ L, A _ {L + 1}, \ldots, A _ {R - 1} \rbrace$ に対応する Binary Trie」に対する探索を行うことができるデータ構造です．応用範囲は広いですが，本記事では次の $2$ つの問題に限定して解説します． $A _ L, … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fwavelet_matrix_basic" title="Wavelet Matrix（基礎） - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:08:50 rich https://info.atcoder.jp/entry/algorithm_lectures/wavelet_matrix_basic 1.0 100%