首页 > 代码库 > 线段树
线段树
线段树(Interval Tree),又叫区间树,顾名思义,它是一棵树,而且是一颗二叉树;树上的每个节点对应于一个区间,线段的起点和终点通常为整数。同一层节点代表的线段不重合,叶子节点的区间是单位长度,不能再分。
一、基本描述
- 树中每个节点表示区间[a,b],对于非叶结点,左儿子[a,(a+b)/2],右儿子[(a+b)/2+1,b]。(除法去尾取整)
- 叶节点长度为1,不能再分。
- 若根节点对应区间为[a,b],则它的深度为log2(b-a+1)+1。(向上取整)
- 线段树为满二叉树,节点度为0或2;若叶节点数目为N,则总结点数为2N-1
二、分解规则
- 分解规则:如果有某个节点代表的区间,完全属于带分解区间,则节点为“终止”节点,不在继续分解。
- 所有“终止”节点所代表的的区间都不重合,且加在一起就覆盖整个低待分解区间。如图,区间[1,9]的线段树上,区间[2,8]分解。
- 区间分解时,每层最多2个“终止”节点,终止节点总数也是log(n)量级的。
线段树上更新叶节点和进行区间分解时间复杂度都是O(log(n))的。线段树能在O(log(n))时间内完成一个区间的建树、插入数据、查找、统计等工作。
三、线段树的构建
- function 以节点v为根建树,v对应区间[l,r]
- {
- 对节点v初始化
- if (l!=r)
- {
- 以v的左孩子为根建树,区间[l,(l+r)/2]
- 以v的右孩子为根建树,区间[(l+r)/2+1,r]
- }
- }
四、线段树的应用
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分,按区间动态进行修改,而且还需要按区间多次进行查询,那么使用线段树可以达到较快查询速度。
用线段树解题,关键是要想清楚每个节点要存哪些信息(当然区间起终点,以及左右子节点指针是必须的),以及这些信息如何高效更新,维护,查询。不要一更新就更新到叶子节点,那样更新效率最坏就可能变成O(n)的了。
先建树,然后插入数据,然后更新,查询。
五、举例
华为16年校招题目:最大数是多少
老师想知道从某某同学当中,分数最高的是多少,现在请你编程模拟老师的询问。当然,老师有时候需要更新某位同学的成绩.
输入描述:
输入包括多组测试数据。 每组输入第一行是两个正整数N和M(0 < N <= 30000,0 < M < 5000),分别代表学生的数目和操作的数目。 学生ID编号从1编到N。 第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩 接下来又M行,每一行有一个字符C(只取‘Q’或‘U’),和两个正整数A,B,当C为‘Q‘的时候, 表示这是一条询问操作,他询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少 当C为‘U’的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
输出描述:
对于每一次询问操作,在一行里面输出最高成绩.
链接:https://www.nowcoder.com/practice/3897c2bcc87943ed98d8e0b9e18c4666?tpId=49&tqId=29275&tPage=1&rp=1&ru=/ta/2016test&qru=/ta/2016test/question-ranking
来源:牛客网
虽然数据量要求不大,普通算法也能做,但是加大数据量的话,还是线段树较好
代码:
1 #include<stdio.h> 2 #include<algorithm> 3 4 using namespace std; 5 #define MY_MAX -9999999; 6 7 struct CNode 8 { 9 int L,R; 10 int nMax; 11 CNode *pLeft, *pRight; 12 }; 13 CNode Tree[300000]; 14 int nMax; 15 int nCount; 16 17 void BuildTree(CNode *pRoot, int l, int r) 18 { 19 pRoot->L=l; pRoot->R=r; pRoot->nMax=MY_MAX; 20 21 if (l!=r) 22 { 23 nCount++; 24 pRoot->pLeft=Tree+nCount; 25 nCount++; 26 pRoot->pRight=Tree+nCount; 27 BuildTree(pRoot->pLeft,l,(l+r)/2); 28 BuildTree(pRoot->pRight,(l+r)/2+1,r); 29 } 30 } 31 32 void Insert(CNode *pRoot, int i, int score) 33 { 34 if (pRoot->L==i && pRoot->R==i) 35 { 36 pRoot->nMax=score; 37 return; 38 } 39 pRoot->nMax=max(pRoot->nMax,score); 40 if (i<=((pRoot->L+pRoot->R)/2)) 41 Insert(pRoot->pLeft,i,score); 42 else 43 Insert(pRoot->pRight,i,score); 44 } 45 46 void QuerynMax(CNode *pRoot,int s,int e) 47 { 48 if (pRoot->nMax<=nMax) 49 return; 50 if (pRoot->L==s && pRoot->R==e) 51 { 52 nMax=max(nMax,pRoot->nMax); 53 return; 54 } 55 if (e<=((pRoot->L+pRoot->R)/2)) 56 QuerynMax(pRoot->pLeft,s,e); 57 else if(s>=((pRoot->L+pRoot->R)/2+1)) 58 QuerynMax(pRoot->pRight,s,e); 59 else 60 { 61 QuerynMax(pRoot->pLeft,s,(pRoot->L+pRoot->R)/2); 62 QuerynMax(pRoot->pRight,((pRoot->L+pRoot->R)/2+1),e); 63 } 64 65 } 66 67 void Updata(CNode *pRoot, int i, int v) 68 { 69 if (pRoot->L==i && pRoot->R==i) 70 { 71 pRoot->nMax=v; 72 return; 73 } 74 75 if (i<=((pRoot->L+pRoot->R)/2)) 76 { 77 Updata(pRoot->pLeft,i,v); 78 } 79 else 80 { 81 Updata(pRoot->pRight,i,v); 82 } 83 pRoot->nMax=max((pRoot->pLeft)->nMax,(pRoot->pRight)->nMax); 84 85 } 86 87 int main() 88 { 89 int M,N; 90 int score; 91 char cmd[10]; 92 int A,B; 93 94 while (scanf("%d%d",&N,&M)!=EOF) 95 { 96 //scanf("%d%d",&N,&M); 97 nCount=0; 98 BuildTree(Tree,1,N); 99 for (int i=1;i<=N;i++) //此处一定要从1开始,与建树匹配。 100 { 101 scanf("%d",&score); 102 Insert(Tree,i,score); 103 } 104 for (int i=0;i<M;i++) 105 { 106 scanf("%s%d%d",&cmd,&A,&B); 107 if (cmd[0]==‘Q‘) 108 { 109 if (A>B) 110 { 111 int temp = B; 112 B=A; 113 A=temp; 114 } 115 116 nMax=MY_MAX; 117 QuerynMax(Tree,A,B); 118 printf("%d",nMax); 119 } 120 else 121 { 122 Updata(Tree,A,B); 123 } 124 125 } 126 } 127 128 return 0; 129 }
线段树