二分法与统计问题江苏淮阴中学李睿.PPT

上传人:国*** 文档编号:767287 上传时间:2018-10-31 格式:PPT 页数:42 大小:179KB
下载 相关 举报
二分法与统计问题江苏淮阴中学李睿.PPT_第1页
第1页 / 共42页
二分法与统计问题江苏淮阴中学李睿.PPT_第2页
第2页 / 共42页
二分法与统计问题江苏淮阴中学李睿.PPT_第3页
第3页 / 共42页
二分法与统计问题江苏淮阴中学李睿.PPT_第4页
第4页 / 共42页
二分法与统计问题江苏淮阴中学李睿.PPT_第5页
第5页 / 共42页
点击查看更多>>
资源描述

1、二分法与 统计问题江苏省淮阴中学 李睿简介l 一定范围内计数问题特点:l 1 描述简单l 2 要求对数据动态维护,动态计算l 解决手段:特殊的统计模式和结构线段树动态处理可以映射在一个坐标轴上的一些固定线段,例如求并区间的总长度,或者并区间的个数等等。优点:随时插入一个区间或删除一个已有区间,并同时用低耗费维护需要的性质。线段树 -构造思想l 下图显示了一个能够表示 1, 10的线段树: 线段树 -动态数据结构TypeTnode=Treenode;Treenode=recordB,E:integer; Count:integer;LeftChild,Rightchild:Tnode;End;其

2、中 B和 E表示了该区间为 B,E; Count为一个计数器,通常记录覆盖到此区间的线段的个数。 LeftChild和 RightChild分别是左右子树的根。 线段树 -静态数据结构l 用数组 B, E, C, LSON,RSON。 设一棵线段树的根为 v。 那么Bv,Ev就是它所表示区间的界。 Cv用来作计数器。 LSONv, RSONv分别表示了它的左儿子和右儿子的根编号。 线段树 -建树l 从根对应的区间 a, b出发,每次分成两个部分,分别建立对应的左右子树,直到面临一个初等区间 x,x+1。线段树 -插入删除线段l 将区间 c,d插入线段树 T(a,b),并设 T(a,b)的根编号为 v l procedure INSERT(c,d;v)l Beginl mid=(Bv+Ev) div 2;l if cBv and Evd then Cv Cv+1l else if cmid then INSERT(c,d;RSONv);l end 线段树 -一个特殊性质举例l 要得到线段树上线段并集的长度,增加一个数据域 Mv, 讨论: l Cv0,Mv = Ev-Bv;l Cv=0 且 v是叶子结点, Mv=0;l Cv=0 且 v是内部结点,Mv=MLSONv+MRSONv; 线段树 -变形,对点统计

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 重点行业资料库 > 1

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。