{"author_name":"atcoder","title":"Wavelet Matrix\uff08\u57fa\u790e\uff09","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fwavelet_matrix_basic\" title=\"Wavelet Matrix\uff08\u57fa\u790e\uff09 - AtCoderInfo\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","description":"\u89e3\u8aac\u52d5\u753b\u306f\u3053\u3061\u3089\u3067\u3059\uff0e 1. \u6982\u8981 \u672c\u8a18\u4e8b\u3067\u306f\uff0cWavelet Matrix \u3068\u3044\u3046\u30c7\u30fc\u30bf\u69cb\u9020\u306b\u3064\u3044\u3066\u89e3\u8aac\u3057\u307e\u3059\u3002 Wavelet Matrix \u3068\u306f\u5927\u96d1\u628a\u306b\u8a00\u3048\u3070\uff0c\u9759\u7684\u306a\u975e\u8ca0\u6574\u6570\u5217 $A=(A_0,A_1,\\ldots,A_{N-1})$ \u306b\u5bfe\u3057\u3066\uff0c\u30af\u30a8\u30ea $(L,R)$ \u304c\u4e0e\u3048\u3089\u308c\u308b\u305f\u3073\u306b\uff0c\u300c\u591a\u91cd\u96c6\u5408 $\\lbrace A _ L, A _ {L + 1}, \\ldots, A _ {R - 1} \\rbrace$ \u306b\u5bfe\u5fdc\u3059\u308b Binary Trie\u300d\u306b\u5bfe\u3059\u308b\u63a2\u7d22\u3092\u884c\u3046\u3053\u3068\u304c\u3067\u304d\u308b\u30c7\u30fc\u30bf\u69cb\u9020\u3067\u3059\uff0e\u5fdc\u7528\u7bc4\u56f2\u306f\u5e83\u3044\u3067\u3059\u304c\uff0c\u672c\u8a18\u4e8b\u3067\u306f\u6b21\u306e $2$ \u3064\u306e\u554f\u984c\u306b\u9650\u5b9a\u3057\u3066\u89e3\u8aac\u3057\u307e\u3059\uff0e $A _ L, \u2026","blog_title":"AtCoderInfo","categories":["\u30c7\u30fc\u30bf\u69cb\u9020","\u533a\u9593\u30af\u30a8\u30ea","Wavelet Matrix","Binary Trie"],"image_url":"https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738","width":"100%","height":"190","provider_name":"Hatena Blog","blog_url":"https://info.atcoder.jp/","version":"1.0","provider_url":"https://hatena.blog","published":"2026-04-10 14:08:50","type":"rich","author_url":"https://blog.hatena.ne.jp/atcoder/","url":"https://info.atcoder.jp/entry/algorithm_lectures/wavelet_matrix_basic"}