数据结构
计算机领域本科教育教学改革试点
工作计划（“101计划”）研究成果
俞勇、张铭、陈越、韩文弢
上海交通大学、北京大学、浙江大学、清华大学
101
12.1线段树
第12章高级查找
戴波
电子科技大学
12.1.1线段树的定义
12.1.2线段树的存储
12.1.3线段树的操作
12.1.4小结
12.1.5作业
12.1.1线段树的定义
12.1.1线段树的定义
数据结构
线段树是满足下面条件的二叉查找树seg_tree：根结点p=1记为seg_tree[p]=v，表示线段区间[l,r]的值是v——例如为查找区间最小值而设计的线段树中，这个值就是区间内所有元素的最小值，如果是为求区间和设计的线段树，这个值就是区间内所有元素的和。区间的长度n=r-l+1。
如果n1:则seg_tree[2p]是区间[l,r]的左儿子的值，表示的范围是[l,(l+r)/2]；seg_tree[2p+1]是区间[l,r]的右儿子的值，表示的范围是[(l+r)/2+1,r]。
如果n=1:seg_tree[p]是叶结点。
12.1.1线段树的定义
12.1.1线段树的定义
数据结构
求[1,14]区间最小值的线段树
说明2：线段树采用二分法进行构造，因此是平衡二叉树，线段树的结点总数=叶结点个数n+内部结点个数n-1=2n-1
说明1：根结点seg_tree[1]=3,即[1,14]范围的最小值是3
12.1.2线段树的存储
12.1.2线段树的存储
数据结构
线段树是二叉查找树，可以采用二叉链表存储，也可以扩充为完全二叉树按照层序编号，用数组存储线段树的数据。
根据完全二叉树用数组存储的性质：第i个结点如果有双亲，双亲在[i/2]（i1）位置，如果有左右孩子，则左孩子在2*i(i1)位置，右孩子在2*i+1(i1|1)。
如下图[1,14]范围求最小值的线段树，圆圈外的数字就是存储在数组的索引。
12.1.3线段树的操作
12.1.3线段树的操作
数据结构
12.1.3线段树的点操作
12.1.3线段树的操作
数据结构
例：修改下面线段树索引7的值为1
如果修改[a,b]范围的索引为k的数据为x，则只需要从根，按照二分搜索方法，判断k与m=(a+b)/2的大小关系，确定线段树的搜索路径，直到到达m=k的叶结点，修改T[k]=x，并在回溯的时候修改沿路的对应的区间值，具体操作如线段树的初始化的思维导图的步骤2所示。
12.1.3线段树的点操作
12.1.3线段树的操作
数据结构
解析：
12.1.3线段树的区间操作
12.1.3线段树的操作
数据结构
如果在[a,b]线段树中求[L,R]范围内的区间结果（比如求最小值/最大值/求和值等），可以采用线段树的区间操作，步骤如下：
首先判断[L,R]是否在线段树范围[a,b]中，如果不在，则区间操作结束，操作结果为0。
否则就在范围内，然后判断范围是否刚好是[a,b]，如果是，则根结点的值就是[L,R]的值；
否则计算m=(a+b)/2,如果Rm,则操作范围缩小在左分支继续；或者Lm，则操作范围缩小在右分支继续；否则左右分支都要进一步进行区间的递归操作。
也就是说，如果区间操作在线段树的某个区间，则先从所在分支向下递归定位所在分支，会覆盖左右分支的部分结点和中间部分结点。其中两侧的结点一直向下递归到子树的L=a,R=b的时候才停止向下，然后回溯。所以左右两侧的最多向下递归到叶结点，中间的在L=a,R=b就停止了。所以最大的递归次数是不超过两侧的树高。
12.1.3线段树的区间操作
12.1.3线段树的操作
数据结构
解析：(1)p=1,m=(1+14)/2=7;3m9，左右子树都进一步求解
(2)p=1的左子树：p=2,m=(1+7)/2=4;3m7，左右子树进一步求解
p=1的右子树：p=3,m=(8+14)/2=11;8m14,左右子树进一步求解
(3）p=2左子树p=4：m=(1+4)/2=2,2m，只到右子树p=9,返回6
p=2的右子树：[5,7]在[3,9]范围之内，返回4
V[3,7]=min(V[3,4],V[5,7])=min(6,5)=5;
(4)p=3的左子树p=6：m=(8+11)/2=9,只到左子树，返回4
(5)V[3,9]=min(V[3,7],V[8,9])=min(5,4)=4
例：快速求出[L,R]区间的最小值V[L,R]，其中1=L=R=14
12.1.3线段树的区间操作
12.1.3线段树的操作
数据结构
例题：已知10000个正整数，用A数组存储这10000个正整数。其中A[i]表示存储的第i个数(1