#算法整理#线段树技巧小结
###线段树学习整理 By 孟一凡
在刷题过程中，常遇到一大类问题，需要将数据映射到坐标轴上的固定线段，线段可互相覆盖，动态取并集。我们解决这类问题常用线段树这种高级数据结构解决问题。
- 线段树构造思想
1.线段树是一颗二叉树。
2.每一个节点表示一个区间[a,b]，叶子节点表示一个单位区间。
3.对于非叶子节点[a,b]，它的左孩子表示区间[a,(a+b)/2]，右孩子表示区间[(a+b)/2+1,b]。
- 线段树逻辑结构
```cpp
typedef struct Node
{
int left; //该节点区间左值
int right; //该节点区间右值
Node *leftchild; //左孩子
Node *rightchild; //右孩子
int cover = 0; //覆盖值
};
```
- 线段树常用操作
```cpp
//建树操作
Node *build(int l,int r)
{
Node *root=new Node;
root->left=l;
root->right=r;
root->leftchild=NUll;
root->cover=0;
root->rightchild=NULL;
if(l+1<r)
{
int mid=(r+l)>>1;
root->leftchild=build(l,mid);
root->rightchild=build(mid+1,r);
}
return root;
}
//插入操作
void Insert(int c,int d,Node *root)
{
if(c<=root->left&&d>=root->right)
{
root->cover++;
}
else
{
if(c<((root->left+root->right)/2))
{
Insert(c,d,root->leftchild)
}
if(d>((root->left+root->right)/2))
{
Insert(c,d,root->rightchild);
}
}
}
//删除操作
void Delete(int c,int d,Node *root)
{
if(c<=root->left&&d>=root->right)
{
root->cover=root->cover-1;
}
else
{
if(c<(root->left+root->right)/2)
{
Delete(c,d,root->leftchild);
}
if(d>(root->left+root->right)/2)
{
Delete(c,d,root->rightchild);
}
}
}
```
#### 线段树相关题目整理
1. 桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？
- 分析
可以将投影抽象为X轴上的线段，求线段覆盖的长度。
- 解法
给线段树每一个节点增加一个域cover，cover=1 表示该节点所对应的区间完全覆盖，cover=0表示该节点所对应的区间未完全覆盖，统计被覆盖区间并集长度
- Code
```cpp
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct Node
{
int left;
int right;
Node *leftchild;
Node *rightchild;
int cover;
};
//插入算法
void Insert(Node *root,int a,int b)
{
int m;
if(root->cover==0)
{
m=(root->left+root->right)/2;
if(a==root->left&&b==root->right)
{
root->cover=1;
}
else if(b<=m)
{
Insert(root->leftchild,a,b);
}
else if(a>=m)
{
Insert(root->rightchild,a,b);
}
else
{
Insert(root->leftchild,a,m);
Insert(root->rightchild,m,b);
}
}
}
//统计算法
int Count(Node *root)
{
int m,n;
if(root->cover==1)
{
return
(root->right-root->left)
}
else
if(root->right-root->left==1)
{
return 0;
}
m=count(root->leftchild);
n=count(root->rightchild);
return m+n;
}
```
投递牛客等公司10个岗位 >
查看14道真题和解析