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; 线段树 -变形，对点统计
