HL分解 (Heavy-Light Decomposition) - ペケンペイのブログ
HL 分解 (heavy-light decomposition) についてではなく、パスクエリを複数の列クエリに分解するという考え方について説明する。HL 分解は木が与えられて次の二種類のクエリを処理する問題等で用いられる。 uv パス上のすべての頂点にxを加算する uv パス上の値の総和を求める 総和クエリの例。この場合は 2+3+4+9+6+4+7+1=36 が答えになる 木ではなく列であれば segment tree によって効率的に処理できる。HL 分解は木をパスに分解することで、木の問題を列の問題に還元する。木をパスに分解するとはどういうことだろうか。例えば次の図のようなものが木をパスに分解した例になっている。 冒頭で例に出したクエリは次の形に分解できる。 このクエリはsum[16..16] + sum[13..14] + sum[0..1] + sum[6..8]で計算できる
Segment Trees
Motivational Problems: http://www.spoj.pl/problems/BRCKTS/ http://www.spoj.com/problems/GSS3/ http://www.spoj.com/problems/HORRIBLE http://www.spoj.pl/problems/IOPC1207/ https://www.spoj.com/problems/GSS2/ http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/ORDERSET/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/TEMPLEQ Segment trees (shortened as segtrees), a
Heavy Light Decomposition
Long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “Basic Idea”. Why a Balanced Binary Tree is good? Balanced Binary Tree A balanced binary tree with N nodes has a height of log N. This gives us the following properties: You need to visit at most log N nodes to reach root node from any other node You need to visit at most 2 * log N nodes to reach fr
キャッシュフレンドリーな二分探索 ー データ構造を再考する | POSTD
現代のコンピュータのアーキテクチャに搭載されている高速のキャッシュメモリは、 参照の局所性 に優れた(＝一連のものとしてアクセスした要素が、互いに近いメモリのアドレスに配置されている)データ構造を好みます。これは、 Boost.Containerの平坦な（ツリー状ではない）連想コンテナ のようなクラスを陰で支えている理論的根拠です。要素を連続的に（かつ順序だてて）保存すると同時に、標準的なC++ノードベースの連想コンテナの機能性をエミュレートします。以下にあるのは、要素が0から30の範囲の時、 boost::container::flat_set の中で 二分探索 がどのように行われるのかを示した例です。 探索で目的の値を絞り込むにつれて、アクセスされる要素は次第に近くなっていきます。そのため、最初のうちは大きな距離を飛び越えていくような感じであっても、参照の局所性は このプロセスの最後の
LCA and RMQ ~簡潔もあるよ！~
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The Unhealthy Obsession with Tree Questions
