QTREE解法的一些研究

SPOJ375QTREEYangZhe∗200713[3],(O(nlogn+qpnlogn)),.——,.Link-CutTreesO((n+q)logn),,.O(n+qlog2n),,SPOJ..SplayTree,O((n+q)logn),SplayTree,.,,“”.,O((n+q)logn).,O(n+qlog2n)..122(DynamicTreeProblems)23Link-CutTrees23.1Link-CutTrees......................................23.2Link-CutTrees......................................33.2.1Access...........................................33.2.2FindRoot.........................................33.2.3Cut............................................33.2.4Join............................................33.2.5....................................43.3Link-CutTrees................................43.3.1(Heavy-LightDecomposition).....................43.3.2PreferredChildO(logn)...................53.3.3SplayO(logn)........................5464.1..............................................64.2()........................................64.2.1SplayTree...............................74.3()................................84.4O(n+qlog2n)()........84.5SplayTreeO((n+q)logn)()...........84.6:,SplayTree,,..........94.7“”O((n+q)logn)()............9¤[e-mail]14.7.1“”.........................................94.7.2..............................94.7.3...............................114.7.4“”...................................114.8.........................................11A121n(n·10000),,,:1.;2..q.2,,.,.,,.,.:.2(DynamicTreeProblems),.,,,.[1].,(,Euler-TourTrees,):,:²MAKETREE()—.²CUT(v)—vparent(v),v.²JOIN(v,w)—vw.v,vw.²FINDROOT(v)—v.,,,,,.3Link-CutTreesLink-CutTreesSleatorTarjan[1].O(logn).Link-CutTrees,,.3.1Link-CutTrees,ACCESS.v,w,wv,wvPre-ferredChild.v,PreferredChild.PreferredChildPreferredEdge.PreferredEdgePreferredPath.,PreferredPath.PreferredPath,,(,,PreferredPath;,PreferredPath).,.,SplayTree.AuxiliaryTree.TPreferredPath,,T.PathParentAuxiliaryTreePreferredPath,PreferredPath,AuxiliaryTreePathParentnull.Link-CutTreesTAuxiliaryTree,PathParentAuxiliaryTree.23.2Link-CutTrees3.2.1AccessACCESSLink-CutTrees.ACCESS(v),vPreferredPath.uparent(u)Pre-ferredChild,parent(u)PreferredChildu,parent(u)PreferredPathparent(u).Link-CutTrees,ACCESS.ACCESS(N)ACCESS(N)Link-CutTreesPathParent,AuxiliaryTreeABCDEFGHIJKLMNOABCDEFGHIJKLMNOABCDEFGHIJKLMNOPreferredEdge,1:Link-CutTrees,ACCESSACCESS,AuxiliaryTree.,,O(logn).,v,PreferredChild.vAuxiliaryTree,vvAuxiliaryTree(vPreferredChild),vvAuxiliaryTree(PreferredChildPreferredPath)vAuxiliaryTree,AuxiliaryTreePathParentv.,vPreferredPath,PathParentu,uuAuxiliaryTree,vAuxiliaryTreeuAuxiliaryTreeu,uAuxiliaryTreeuPathParentu.,PreferredPath.3.2.2FindRootACCESS(v),vAuxiliaryTree.vAuxiliaryTree.v,AuxiliaryTree,,.SplayTreeAuxiliaryTree,Splay.3.2.3Cutv,vAuxiliaryTree,vAuxiliaryTree,.3.2.4Joinv,vAuxiliaryTreePathParentw,v.33.2.5Link-CutTrees:1:procedureAccess(v)2:uÃv3:vÃnull4:repeat5:Splay(u)6:path-parent[right-child[u]]Ãu7:right-child[u]Ãv8:path-parent[v]Ãnull9:vÃu10:uÃpath-parent[u]11:untilu=null12:endprocedure13:functionFindRoot(v)14:Access(v)15:Splay(v)16:whileleft-child(v)6=nulldo17:vÃleft-child(v)18:endwhile19:Splay(v)20:returnv21:endfunction22:procedureCut(v)23:Access(v)24:left-child[v]Ãnull25:endprocedure26:procedureJoin(v,w)27:Access(v)28:path-parent[v]Ãw29:Access(v)30:endprocedure3.3Link-CutTrees,ACCESS,O(logn).ACCESS.ACCESS,ACCESS.Pre-ferredChildO(logn);ACCESSSplayO(logn).3.3.1(Heavy-LightDecomposition),,(Heavy),(Light).size(i)i.uvsize(u)(,),(v,u),vw(v,w)(size(w)=size(u)).1,.:3.1uv,(v,u),size(u)size(v)/2.1,.,size(u)12size(v)(v,u).4size(u)¸size(v)/2,(v,u),v(v,w).,size(v)¸1+size(w)+size(u)¸2size(u)+1¸1+size(v).!¥light-depth(v)v,3.1light-depth(v)·lgn.3.1,,.n,v1,lgn.¥3.3.2PreferredChildO(logn)PreferredChild,T.vPreferredChild,PreferredChild,PreferredEdge.PreferredEdge.3.1,ACCESSlgnPreferredEdge.PreferredEdge.PreferredEdge?PreferredEdgePreferredEdge(PreferredEdge).PreferredEdge,PreferredEdge,PreferredEdgePreferredEdge.ACCESSPreferredEdgeO(logn).,PreferredChildO(logn).3.3.3SplayO(logn)Splay.SplayTreeuw(u),s(u)u.Φ=Pulgs(u).:3.2SPLAY(v)zig-zig,zag-zagdcost·3(lgs0(v)¡lgs(v)).(3.)3.3SPLAY(v)zig-zag,zag-zigdcost·2(lgs0(v)¡lgs(v))·3(lgs0(v)¡lgs(v)).3.4SPLAY(v)zig,zagdcost·lgs0(v)¡lgs(v)+1·3(lgs0(v)¡lgs(v))+1.,.:3.5(AccessTheorem)SPLAY(v)dcost·3(lgs0(v)¡lgs(v))+1.(3.),ACCESS(O(logn))SPLAY,w(u)=1.AuxiliaryTree,PathParent,1+().w(u)=1+uPathParent,s(u)u.5ACCESS(v),v0=v,v1=path-parent[v0],...,vk=path-parent[vk¡1]SPLAY,ACCESSdcost·kXi=03`lgs0(vi)¡lgs(vi)´+1·3kXi=1`lgs0(vi)¡lgs0(vi¡1)´+lgs0(v0)¡lgs(v0)#+k=3`lgs0(vk)¡lgs(v0)´+k·3lgn+PreferredChildPreferredChildO(logn),ACCESSO(logn).44.1,.,1.,Link-CutTreesO((n+q)logn),O(n+qlog2n),SplayTreeO((n+q)logn),“”O((n+q)logn)1:,2.QTREEdynamic-treelink-cut-trees.pas4.58()QTREEheavy-light-decompositionsegment-tree.pas2.65()QTREEheavy-light-decompositionimaginary-bst.pas2.37QTREEheavy-light-decompositionsplay-tree.pas4.28QTREEheavy-light-decompositionglobal-balanced-bst.pas2.062:,,,,.,,.4.2()Link-CutTrees,AuxiliaryTree,AuxiliaryTree,cost,costmaxcost.,maxcostAuxiliaryTreeO(1).,AuxiliaryTreecost,SplayAuxiliaryTreemaxcost.,O(logn).uv,ACCESS(u),ACCESS(v),(u)Aux