资源描述：
《lecture 11 augmenting data structures, dynamic order statistics, interval trees》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、MITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Pleaseusethefollowingcitationformat:ErikDemaineandCharlesLeiserson,6.046JIntroductiontoAlgorithms,Fall2005.(MassachusettsInstituteofTechnology:MITOpenCourseWare).http://ocw.mit.edu(accessedMMDD,YYY
2、Y).License:CreativeCommonsAttribution-Noncommercial-ShareAlike.Note:Pleaseusetheactualdateyouaccessedthismaterialinyourcitation.FormoreinformationaboutcitingthesematerialsorourTermsofUse,visit:http://ocw.mit.edu/termsMITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiont
3、oAlgorithms,Fall2005Transcript–Lecture11Goodmorning.Todaywe'regoingtotalkaboutaugmentingdatastructures.Andthisisa--Normally,ratherthandesigningdatastructuresfromscratch,youtendtotakeexistingdatastructuresandbuildyourfunctionalityintothem.Andthatisaprocesswecalldata-struc
4、tureaugmentation.Andthisalsotodaymarkssortofthestartofthedesignphaseoftheclass.Wespentalotoftimedoinganalysisuptothispoint.Andnowwe'restillgoingtolearnsomenewanalyticaltechniques.Butwe'regoingtostartturningourfocusmoretowardhowisitthatyoudesignefficientdatastructures,eff
5、icientalgorithmsforvariousproblems?Sothisisagoodexampleofthedesignphase.Itisareallygoodidea,atthispoint,ifyouhavenotdoneso,toreviewthetextbookAppendixB.Youshouldtakethatasadditionalreadingtomakesurethatyouarefamiliar,becauseoverthenextfewweekswe'regoingtohitalmosteveryto
6、picinAppendixB.Itisgoingtobebroughttobearonthesubjectsthatwe'retalkingabout.Ifyou'regoingtogoscrambletolearnthatwhileyou'realsotryingtolearnthematerial,itwillbemoreonerousthanifyoujustsimplyreviewthematerialnow.We'regoingtostartwithanillustrationoftheproblemofdynamicorde
7、rstatistics.Wearefamiliarwithfindingthingslikethemedianorthekthorderstatisticorwhatever.Nowwewanttodothesamethingbutwewanttodoitwithadynamicset.Ratherthanbeinggivenallthedataupfront,we'regoingtohaveaset.Andthenatsomepointsomebodyisgoingtobedoingtypicallyinsertanddelete.A
8、ndatsomepointsomebodyisgoingtosayOK,selectformetheithlargestguyortheithsmallestguy----inthedynamicset.O
