工学类工学特论.doc

童梦无忧网 试管婴儿论坛 本文由defang168贡献 ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 工学特論 定兼 邦彦 2006年11月1日 木構造BP表現 木括弧列表現 内部節点: () 葉:() : 1 2 4 5 6 1 2 3 4 5 6 7 8 9 10 11 2 3 7 9 8 10 11 2n+o(n) bits ? ( 位置表現 ()()()()()()() 可能演算 定数時間 親(移動) 長男 次兄弟 子孫数 子数 i 番目子 深 深 d 祖先 lca BP O(子数) O(i) DFUDS 3 括弧列操作 ? ? ? rankp(P,i): P1.i 中 p 数返 selectp(P,i): P 中 i 番目 p 位置返 findclose(P,i): Pi ( 対応 )位置返 enclose(P,i): Pi ( 囲括弧位置返 1 2 4 5 6 3 7 9 8 10 11 enclose findclose 7 8 9 10 11 1 2 3 4 5 6 P()()()()()()() rank()(P,10) = 3 4 木巡回 ? ? ? ? ? 2 4 5 6 P: 木括弧列表現 ( 位置表 root() = 1 parent(v) = enclose(P,v) firstchild(v) = v + 1 sibling(v) = findclose(P,v) + 1 1 3 7 9 8 10 5 enclose 11 findclose 7 8 9 10 11 1 2 3 4 5 6 ()()()()()()() 深 Pi = rank(P,i) ? rank)(P,i) depth(v) = Pv ? PP計算 1 2 4 5 6 3 7 9 8 10 11 1 2 3 4 5 6 7 8 9 10 11 P ()()()()()()() P 1212343432321232321210 6 子孫数 (部分木大) v 根部分木大 subtreesize(v) = (findclose(P,v)?v+1)/2 1 2 4 5 6 3 7 9 8 10 7 11 1 2 3 4 5 6 7 8 9 10 11 P ()()()()()()() findclose構造 括弧列長 B = ? log n 分割 b(p): p 番号 (p): p 括弧位置 括弧 p far ? b(p) b(p) far 開括弧 p opening pioneer ? p 直前 far 開括弧 q 対 b(p) b(q) ? opening pioneer対応括弧位置0,1 表現 r ( q p ( ( (p) (q) (r) ) ) ) 8 補題: 数 ，opening pioneer数 2?3 以下 証明: 各，(b(p), b(p) 枝 外平面 opening/closing pioneer再BP = n/B = 2n/log n ? BP長 O(n/log n) 再帰深 2 十分 9 findclose ? ? ? ? ? (p) = findclose(P,p) 求 p far (p) 求 p 直前 pioneer p* 求 pioneer括弧列用(p*) 求 p pioneer， b(p) = b(p*) pp*深差，(p) 位置決 p* p ( ( (p) (p*) ) ) 10 enclose (p) = enclose(P,p) ? b(p) = b(p) (p) 表引求 ? b(p) b(p) 括弧位置記憶 対応括弧位置記憶 括弧複数場合一番外側記憶 括弧抜出再帰 ( ( ()( ) ) ) 11 lca計算 lca = lowest common ancestor ? u = lca(v,w): v w 共通祖先 最根遠 ? 定数時間計算可 w u v 12 Pi = rank(P,i) ? rank)(P,i) u = parent(RMQP(v,w)+1) m = RMQP(v,w): Pv.w 中最小値添字 (RMQ = Range Minimum Query) u 1 2 3 4 7 w 9 8 10 11 1 2 3 4 5 6 7 8 9 10 11 v P ()()()()()()() P 1212343432321232321210 u v mw 5 6 13 Range Minimum Query 問題 (RMQ) ? 入力: 配列 A1,n (前処理可), 区間 i,j ? 1,n ? 出力: 部分配列 Ai,j 中最小値添字 補題: 長 n 配列対構造 s(n), 問合時間 t(n) ，以下 式満構造 O(n) 時間作成可. 8n ? t (n) = O(1) + t ? ? lg n ? ? ? ? ? 8n ? s ( n) = 4n + s? ? lg n ? + o(n) ? ? ? 14 Cartesian Tree 配列 A1,n 対Cartesian tree 根: A1,n 最小値 Ai 格納 左部分木: A1,i?1 対Cartesian tree 右部分木: Ai+1,n 対Cartesian tree A 143504537 0 1 3 4 5 4 5 7 15 3 Cartesian TreeRMQ関係 RMQ(i,j) = lca(i,j) A 143504537 0 1 3 4 5 4 5 7 16 3 Cartesian Tree性質 補題: A1,n?1 対木 An 追加， An 根最右葉上存在 証明: An 配列中一番右要素 左子 0 1 2 0 4 6 3 4 5 4 4 5 3 3 54 5 6 17 1 2 Cartesian Tree作成 A1,n?1 対木 An 追加 ? An?1 根要素順比較 ? An 小要素 x 現，挿入 ? x 右子 An 左子 1 1 3 3 4 4 5 18 4 5 計算量 補題: Cartesian tree O(n) 時間構成可 証明: Ai 挿入比較回数 ci ， n 全体計算量 O(c ) i =1 i Cartesian tree最右上各， Ai 挿入後左子，一度 Ai 比較，比較回数和 n 以下 計算量 O(n) 19 Cartesian Tree括弧列表現 A 143504537 0 1 3 4 3 4 5 5 7 ()()()()()()()()() 1 4 3 5 0 4 5 3 7 20 RMQ 配列 A1,n Cartesian tree変換 ? Cartesian tree括弧列 P, 深列 P 変換 Ai,j 最小値位置 m 求 ? i = select()(P,i), j = select()(P,j) ? Pi, j 最小値位置 m ， m = rank()(P,m)+1 21 PRMQ P 長 w = (lg n)/2 分割 ? 各中最小値配列 B 表 ? Pi, j 最小値以下 i 含中最小値 j 含中最小値 間最小値 P ()()()()()()() P 1212343432321232321210 B 1 3 2 1 1 0 22 計算量 P 長: 4n ? B 長: 4n/w = 8n/lg n ? 計算量 ? 8n ? t (n) = O(1) + t ? ? lg n ? ? ? ? ? 8n ? s ( n) = 4n + s? ? lg n ? + o(n) ? ? ? 定理: RMQ 4n+o(n) 構造 用定数時間計算 23 Sparse Table 配列 B1,m 各区間i,i+2k?1 最小値求Mi,k 格納. ( i = 1 ,m , k = 1 ,2, ? ,lg m ) 問合区間 s,b 与 1. k = lg(b?s) 2. Ms, k Mb?2k+1, k 比較,小解 出力. O(1) 時間，O(m lg2 m) bit 領域 ? B 長 O(n/lg3 n) 用 ?o(n) bit領域 24 定数時間select 長 M 0,1，N 個要素1 N = O(M/lg M) 21間距離 (lg M)c (仮定) (仮定) s = M/N, t = lg M/(2c lg lg M) ? 配列 A1: 1位置 t 置格納 (N lg M)/t = O(M lg lg M/lg M) bits 配列 A2: 1間距離格納 N ? c lg l