Data Structures Advanced

《Data Structures Advanced》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DataStructuresAdvancedBasicReviewListGraphQueueTreeStackLet’sgofurther…DSforinterval…O(logn)?Justbinary!SegmentTree[1,4][1,4][1,2][1,2][3,4][3,4][1,1][1,1][[[2,2][2,2]]][3,3][3,3][4,4][4,4]SegmentTreeSegmentTree2k-1>=nk<=lognO(logn)SegmentTreeMakeTreeNODE.MIDSegmentTreeQuery&

2、UpdateSituation1Situation2Situation3SegmentTreeupdateSegmentTreequerySegmentTreeSegmentTreeRMQNODE.MIDSegmentTreeMAX(X)=MAX(MAX(X1),MAX(X2))x2x1xSegmentTree[1,4][1,4]12306[1,2][1,2]23[3,4][3,4]12306[1,1][1,1]22[[[2,2][2,2]]][3,3][3,3]12306[4,4][4,4]3123SegmentTreeBuddySystemStart1024A=70KA12825651

3、2B=35KAB64256512C=80KAB64C128512Afree128B64C128512D=60K128BDC128512Bfree12864DC128512Dfree256C128512Cfree512512End1024ReferfromcoolshellSegmentTree[1,1024][1,1024]0:896[1,512][1,512]0:384[513,1024][513,1024]1:512[1,256][1,256][[[257,512][257,512]]][513,768][513,768][769,1024][769,1024]1:2560:01:25

4、61:256UFSet55227733661144UFSetNodeUFSetfindParent11223344UFSetO(n)findParentUFSetPathCompress4411112222333344UFSetPathCompress4411221133223344UFSetPathCompress4411221133223344UFSetPathCompressOptimize1UFSetUnionbyrank55Eg1.Union(4,5)1166227733889944UFSetUnionbyrankEg.Union(3,5)665544771122338899UF

5、SetUnionbyrankEg.Union(3,5)665544771122338899Root(3)!=Root(5)UFSetUnionbyrankEg2.Union(3,6)116622335544UFSetUnionbyrankEg2.Union(3,6)113366224455Root(3)==Root(6)UnionbyrankUFSetOptimize2SkipListReferfromODSSkipListOffline11991155991133557799112233445566778899SegmentTreeOnline?SkipListCointossingSk

6、ipListSkipListAnEfficientSSet…SkipListOrder?ContainX?SkipListSkipListSkipListSkipListSkipListAnEfficientRandom-AccessListSkipListKth?Rank?SkipListSkipListLstL+1L1L2sxtThanks