natsugiri https://blog.hatena.ne.jp/natsugiri/ でも今日はSRMあるから https://natsugiri.hatenablog.com/ データ構造 概要 固定長二進パトリシアツリー 目標 初期化：長さ 2^64 の理想配列 a, 全ての要素は値型の最大値で初期化される 更新 (key, value) : a[key] を value に書き換える 質問 (left, right) ：min(a[left], ..., a[right]) を出力する keyが符号なし64bitであるような、大きなセグツリーを作る トライで実装するとその頂点数は更新の回数と高さの積になってしまう。パトリシアツリーならば頂点数は更新の回数の2倍で抑えられる。 そのような長さが64固定の二進パトリシアツリーを作り、分枝ノードには min を乗せる。 実装 頂点 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnatsugiri.hatenablog.com%2Fentry%2F2025%2F07%2F21%2F210416" title="セグツリーをパトリシアツリーで実装する - でも今日はSRMあるから" 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 2025-07-21 21:04:16 rich https://natsugiri.hatenablog.com/entry/2025/07/21/210416 1.0 100%