首页 > 代码库 > 线段树

线段树

  线段树(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 }
View Code

 

  

线段树