首页 > 代码库 > 线段树

线段树

2024-09-05 19:32:29   258人阅读

　　线段树（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

 

　　

线段树


联系
我们