ツリーの重軽分解：長子優先によるパス操作の高速化
セグメント木は、配列上の区間和や最大値などの情報を効率的に管理するためのデータ構造であり、クエリや更新を \(O(\log n)\) で処理できる。しかし、問題が「配列」ではなく「木構造」に拡張され、任意の2ノード間のパス上の情報を維持・操作したい場合、単純にセグメント木を適用することはできない。
木上のパスを線形構造に変換するアイデア
木は分岐構造を持つため ...
8月19日 04:01 投稿
樹における最近共通祖先の効率的計算手法
木構造上の2頂点間の最近共通祖先（Lowest Common Ancestor, LCA）を高速に求めるには、複数のアルゴリズムが存在します。本稿では、倍増法、オイラー巡回＋RMQ、および木の重軽分解（Heavy-Light Decomposition）の3つの代表的手法について、それぞれの設計思想・実装構造・計算量特性を解説します。
倍増法によるLCAクエリ
各頂点から根方向へ2kステップ先の祖先とその ...
8月5日 03:47 投稿
木の連鎖分解（ヘビーライト分解）のまとめ
木の連鎖分解（ヘビーライト分解）のまとめ
基本概念
基本的な考え方
実装手順
ステップ1: 重い子、重い連鎖
ステップ2: dfn順序
ステップ3: 時間計算量の分析
コード実装
重い子の検出
連鎖分解
各種操作
LCAの計算：
パス更新：
パスクエリ：
推奨問題
基本概念
基本的な考え方
\qquad 木の連鎖分解、名前の通り、木データ構造に適用され ...
5月28日 14:42 投稿