"セグメント木はlog N層の構造であり再帰的に考える必要 + 平方分割は2層しかないので考えやすい / キャッシュが効きやすく，上手に実装したセグメント木と比べても3〜5倍遅くなる程度"

sh19910711 のブックマーク 2021/12/18 08:16

<blockquote class="hatena-bookmark-comment"><a class="comment-info" href="https://b.hatena.ne.jp/entry/4659211145821704769/comment/sh19910711" data-user-id="sh19910711" data-entry-url="https://b.hatena.ne.jp/entry/s/kujira16.hateblo.jp/entry/2016/12/15/000000" data-original-href="https://kujira16.hateblo.jp/entry/2016/12/15/000000" data-entry-favicon="https://cdn-ak2.favicon.st-hatena.com/64?url=https%3A%2F%2Fkujira16.hateblo.jp%2Fentry%2F2016%2F12%2F15%2F000000" data-user-icon="/users/sh19910711/profile.png">セグメント木をあきらめた人のための平方分割 - くじらにっき++</a><ul class="comment-tag" style="list-style: none; margin: 0px;"><li style="float: left">[<a href="https://b.hatena.ne.jp/q/%2Aalgorithm">*algorithm</a>]</li><li style="float: left">[<a href="https://b.hatena.ne.jp/q/%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0">データ構造</a>]</li></ul><br><p style="clear: left"> &quot;セグメント木はlog N層の構造であり再帰的に考える必要 + 平方分割は2層しかないので考えやすい / キャッシュが効きやすく，上手に実装したセグメント木と比べても3〜5倍遅くなる程度&quot;</p><a class="datetime" href="https://b.hatena.ne.jp/sh19910711/20211218#bookmark-4659211145821704769"><span class="datetime-body">2021/12/18 08:16</span></a></blockquote><script src="https://b.st-hatena.com/js/comment-widget.js" charset="utf-8" async></script>

このブックマークにはスターがありません。
最初のスターをつけてみよう！

セグメント木をあきらめた人のための平方分割 - くじらにっき++

kujira16.hateblo.jp2016/12/16

この記事はCompetitive Programming Advent Calendar 2016（その2）の12月15日の記事です。 www.adventar.org はじめに基本事項 1点に対する変更クエリ・区間に対する質問クエリ Range Sum Query Range Minimum ...

15 人がブックマーク・1 件のコメント

他のコメントを読む

＼コメントがサクサク読めるアプリです／

はてなブックマーク

セグメント木をあきらめた人のための平方分割 - くじらにっき++

はてなブックマーク

公式Twitter

はてなのサービス