工学类工学特论.ppt

工学特論 定兼邦彦2006年11月1日 2 木構造 BP表現 木 括弧列 表現内部節点 葉 2n o n bits 位置 表現 1 3 8 4 2 5 6 7 9 10 11 3 可能 演算 定数時間 4 括弧列 操作 rankp P i P 1 i 中 p 数 返 selectp P i P中 i番目 p 位置 返 findclose P i P i 対応 位置 返 enclose P i P i 囲 括弧 位置 返 findclose enclose rank P 10 3 1 3 8 4 2 5 6 7 9 10 11 P 5 木 巡回 P 木 括弧列表現 位置 表 root 1parent v enclose P v firstchild v v 1sibling v findclose P v 1 findclose enclose 1 3 8 4 2 5 6 7 9 10 11 6 P i rank P i rank P i depth v P v P P 計算 1212343432321232321210 P P 1 3 8 4 2 5 6 7 9 10 11 深 7 v 根 部分木 大 subtreesize v findclose P v v 1 2 P 1 3 8 4 2 5 6 7 9 10 11 子孫 数 部分木 大 8 findclose 構造 括弧列 長 B logn 分割b p p 番号 p p 括弧 位置括弧p far b p b p far開括弧p openingpioneer p 直前 far開括弧q 対 b p b q openingpioneer 対応 括弧 位置 0 1 表現 9 補題 数 openingpioneer 数 2 3以下 証明 各 b p b p 枝 外平面 opening closingpioneer 再 BP n B 2n logn BP 長 O n logn 再帰 深 2 十分 10 findclose p findclose P p 求 p far p 求 p 直前 pioneerp 求 pioneer 括弧列 用 p 求 p pioneer b p b p p p 深 差 p 位置 決 p p p p 11 enclose p enclose P p b p b p p 表引 求 b p b p 括弧 位置 記憶対応 括弧 位置 記憶括弧 複数 場合 一番外側 記憶括弧 抜 出 再帰 12 lca 計算 lca lowestcommonancestoru lca v w v w 共通 祖先 最 根 遠 定数時間 計算可 13 P i rank P i rank P i u parent RMQP v w 1 m RMQP v w P v w 中 最小値 添字 RMQ RangeMinimumQuery 1212343432321232321210 v v w u w m u P P 1 3 8 4 2 5 6 7 9 10 11 14 RangeMinimumQuery 問題 RMQ 入力 配列A 1 n 前処理可 区間 i j 1 n 出力 部分配列A i j 中 最小値 添字補題 長 n 配列 対 構造 s n 問 合 時間 t n 以下 式 満 構造 O n 時間 作成可 15 CartesianTree 配列A 1 n 対 Cartesiantree 根 A 1 n 最小値A i 格納左部分木 A 1 i 1 対 Cartesiantree右部分木 A i 1 n 対 Cartesiantree 7 3 5 4 0 5 3 4 1 16 CartesianTree RMQ 関係 RMQ i j lca i j 7 3 5 4 0 5 3 4 1 17 CartesianTree 性質 補題 A 1 n 1 対 木 A n 追加 A n 根 最右葉 上 存在 証明 A n 配列中 一番右 要素 左 子 5 3 4 1 6 4 2 0 18 A 1 n 1 対 木 A n 追加 A n 1 根 要素 順 比較 A n 小 要素x 現 挿入x 右 子 A n 左 子 CartesianTree 作成 19 計算量 補題 Cartesiantree O n 時間 構成可証明 A i 挿入 比較回数 ci 全体 計算量 Cartesiantree 最右 上 各 A i 挿入後 左 子 一度 A i 比較 比較回数 和 n以下 計算量 O n 20 CartesianTree 括弧列表現 0 1 3 4 5 4 5 3 7 1 4 3 5 0 4 5 3 7 21 RMQ 配列A 1 n Cartesiantree 変換Cartesiantree 括弧列P 深 列P 変換A i j 最小値 位置m 求 i select P i j select P j P i j 最小値 位置 m m rank P m 1 22 P RMQ P 長 w lgn 2 分割各 中 最小値 配列B 表 P i j 最小値 以下 i 含 中 最小値j 含 中 最小値 間 最小値 1212343432321232321210 P P B 1 3 2 1 1 0 23 計算量 P 長 4nB 長 4n w 8n lgn計算量定理 RMQ 4n o n 構造 用 定数時間 計算 24 SparseTable 配列B 1 m 各区間 i i 2k 1 最小値 求 M i k 格納 i 1 m k 1 2 lgm 問 合 区間 s b 与 k lg b s M s k M b 2k 1 k 比較 小 解 出力 O 1 時間 O mlg2m bit領域B 長 O n lg3n 用 o n bit領域 25 定数時間select 長 M 0 1 N個 要素 1N O M lgM 仮定 2 1 間 距離 lgM c 仮定 s M N t lgM 2clglgM 配列A1 1 位置 t置 格納 NlgM t O MlglgM lgM bits配列A2 1 間 距離 格納N clglgM