ACM算法讲座-线段树.ppt

1、ACM算法讲座,线段树及其应用 06 基础数学 描述集合论 汪方,什么线段树： 线段树是用一种树状结构来存储一个连续区间的信息的数据结构。 线段树有什么用： 它主要用于处理一段连续区间的插入,查找,统计,查询等操作。 复杂度： 设区间长度是n,所有操作的复杂度是logn级别。,线段树的存储结构（例1）：,叶子结点划分到区间长度为1。,线段树的存储结构（例2）：,假设有一个数列 30 70 50 80用线段树来存储 叶子节点划分到区间长度为0，即一个点。,80,80,70,50,80,30,70,1 - 2,3 - 4,4 - 4,3 - 3,2 - 2,1 - 1,线段树的实现（以例2的为例）

2、,用一个struct存储： 基本域：左右边界：ld，rd。 左右孩子：lc，rc。 信息域：key。 typedef struct node int ld，rd； struct node *lc， *rc； keytype key； node；,建空树,建立一个从区间是a到b的空线段树： node* buildtree( int a, int b ) node* p = 给p申请一块内存 p - ld = a; p - rd = b; 初始化p-key if ( a = b ) return p; p - lc = buildtree( a, ( a + b ) / 2 ); p - rc =

3、 buildtree( ( a + b ) / 2 + 1, b ); return p; ,插入线段a,b,void insert( node *T, int a, int b, keytype key ) if ( a ld 根据T-lc和T-rc的信息处理T-key ,查找线段a,b的key值,keytype search( node *T, int a, int b ) keytype res; if ( a ld ,线段树的性质,1,线段树是平衡的2叉树,最大深度logn(n为线段树所表示区间的长度) 2,任意的线段a,b在线段树的查询或查找过程中把这个线段最多分成log(b-a)份

4、 证明略。 以上2条性质保证了线段树除建树外的操作都是log(n)级别的复杂度。,例题1：rmq问题的线段树解法,rmq问题的标准解法是O(nlogn)的预处理, O(1)的查询. 不过线段树可以实现O(nlogn)的预处理,O(logn)的查询,速度也不错。 以求最大值为例，将key定义为区间的最大值。建树时初始化为负无穷。 把任意点a看成是区间a,a，先把所有的点插入线段树。然后每次用线段树去查询。,例题1：rmq问题的线段树解法,void insert( node *T, int pos, int key ) if ( T - ld = T - rd ) T - key = key; r

5、eturn; if ( pos ld + T - rd ) / 2 ) insert( T - lc, pos, key ); else insert( T - rc, pos, key ); T - key = max( T - lc - key, T - rc - key ); ,例题1：rmq问题的线段树解法,int search( node *T, int a, int b ) int res = 负无穷; if ( a ld ,例题2：pku3321 Apple Tree,一颗有N(N 100000)个节点的苹果树，开始每个节点上有一个苹果。然后有M(M 100000)条语句，语句分

6、2种形式： “C x”表示如果第x个节点上有苹果，则把苹果摘去，如果没有，则在这个结点上长出一个苹果。 “Q x”表示询问此时树上有多少苹果。 要求对于每条“Q x”语句输出相应的苹果数。,例题2：pku3321 Apple Tree,输入：第1行是整数N，接下来N1行表示这颗树的边，然后是整数M和M条语句。 输出：对于每条“Q x”输出相应的苹果数。 样例输入： 样例输出： 3 3 1 2 2 1 3 3 Q 1 C 2 Q 1,例题2：pku3321 Apple Tree,分析：如果我们模拟建树，然后对于每条语句都做相应的处理，由于对于“Q x”语句需要遍历一颗树，那么肯定要tle。 对树

7、进行一次遍历，并按照遍历的顺序给树重新标号，那么所有的子树的节点的标号都是连续的区间。 这样“C x”就变成了对一个点的操作。“Q x”变成了对一个区间的和的查询，这两种操作都可以通过线段树来完成。,例题2：pku3321 Apple Tree,核心代码： void convert( tree *T, int a ) if ( T - ld = T - rd ) T - key = 1; return; if ( a ld + T - rd ) / 2 ) convert( T - lc, a ); else convert( T - rc, a ); T - key = T - lc - key + T - rc - key; ,例题2：pku3321