一、线段树的定义
首先，线段树是一棵完全二叉树。它的特点是：每个结点表示的是一个线段，或者说是一个区间。事实上，一棵线段树的根结点表示的是“整体”区间，而它的左右子树也是一棵线段树，分别表示区间的左半边和右半边。树中的每个结点表示一个区间[a,b]。每一个叶子结点表示一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左孩子表示的区间为[a,(a+b)/2]，右孩子表示的区间为[(a+b)/2,b]。 用T(a,
b)表示一棵线段树，参数a,b表示区间[a,b]，其中b-a称为区间的长度，记为L。
线段树T(a,b)也可递归定义为：
若L>1 : [a, (a+b)/ 2]为T的左孩子； [(a+b) / 2,b]为T的右孩子。 若L=1 : T为叶子节点。
下图就是一棵线段树：
二、线段树的实现(C++)
2.1 结点定义：
class regionTreeNode
{
public:
int left; //左端点值
int right; //右端点值
int cover; //被覆盖的次数
regionTreeNode *leftChild; //指向左孩子的指针
regionTreeNode *rightChild; //指向右孩子的指针
regionTreeNode(): left(0), right(0), cover(0), leftChild(NULL), rightChild(NULL){} //构造函数
};
2.2 建立线段树
//建立二叉树
//min和max分别表示线段的左端点和右端点
regionTreeNode* createRegionTree(int min, int max)
{
if (max - min < 1)
{
cout<<"输入的参数不合法！";
return NULL;
}
regionTreeNode *rootNode = new regionTreeNode();
rootNode->left = min;
rootNode->right = max;
rootNode->cover = 0;
rootNode->leftChild = NULL;
rootNode->rightChild = NULL;
//叶子结点
if (max - min == 1)
{
return rootNode;
}
else if (max - min > 1)
{
int mid = (min + max) >> 1;
rootNode->leftChild = createRegionTree(min, mid); //递归构造左子树
rootNode->rightChild = createRegionTree(mid, max); //递归构造右子树
}
return rootNode;
}
2.3在一棵线段树里插入一条线段
//插入一条线段
//a:插入线段的左端点
//b:插入线段的右端点
//tree:插入线段树的根结点
void insertRegion(int a, int b, regionTreeNode *tree)
{
if (tree == NULL || a < tree->left || b > tree->right)
{
cout<<"输入的参数不合法！";
return;
}
if (tree->left == a && tree->right == b)
{
tree->cover++;
return;
}
int mid = (tree->left + tree->right) >> 1;
if (b <= mid)
{
insertRegion(a, b, tree->leftChild);
}
else if (a >= mid)
{
insertRegion(a, b, tree->rightChild);
}
else
{
insertRegion(a, mid, tree->leftChild);
insertRegion(mid, b, tree->rightChild);
}
}
2.4在一棵线段树里删除一条线段
//删除一条线段
//c:删除线段的左端点
//d:删除线段的右端点
//tree:删除线段树的根结点
void deleteRegion(int c, int d, regionTreeNode *tree)
{
if (tree == NULL || c < tree->left || d > tree->right)
{
cout<<"输入的参数不合法！";
return;
}
if (c == tree->left && d == tree->right)
{
tree->cover--;
return;
}
int mid = (tree->left + tree->right) >> 1;
if (d <= mid)
{
deleteRegion(c, d, tree->leftChild);
}
else if (c >= mid)
{
deleteRegion(c, d, tree->rightChild);
}
else
{
deleteRegion(c, mid, tree->leftChild);
deleteRegion(mid, d, tree->rightChild);
}
}
三、线段树的典型应用
题目：桌子上零散地放着若干个盒子，桌子的后方是一堵墙。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？
这道题目是一个经典的模型。在这里，我们可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。
用线段树来求解：
给线段树每个节点增加一个域cover。cover=1表示该结点所对应的区间被完全覆盖，cover=0表示该结点所对应的区间未被完全覆盖。
代码如下：
struct SegmentTreeNode //首先定义一个线段树节点的数据结构：
{
int a; //线段起点
int b; //线段终点
bool cover; //是否被全部覆盖
int color; //线段的颜色
SegmentTreeNode *left;
SegmentTreeNode *right;
};
我们首先在给定的线段区间上去构建一颗完全二叉树，作为我们线段树的一棵基树
SegmentTreeNode* createTree(int m, int n) //构建一棵完全二叉树，作为线段树的基树
{
SegmentTreeNode *root = new SegmentTreeNode();
root->a = m;
root->b = n;
root->cover = false;
root->color = 0;
root->left == NULL;
root->right == NULL;
if((n - m) == 1)
{
return root;
}
else if(n - m > 1)
{
int mid =(m + n) >> 1;
root->left = createTree(m, mid);
root->right = createTree(mid, n);
}
return root;
}
然后我们将用到的线段插入到基树当中，去更新基树的cover域：
void Insert(SegmentTreeNode *root, int m, int n) //求解覆盖总长度的问题
{
if(root->cover == true || root == NULL)
{
return;
}
int mid = (root->a + root->b) >> 1;
if(m == root->a && n == root->b)
{
root->cover = true;
}
else if(m >= mid)
{
Insert(root->right, m, n);
}
else if(n <= mid)
{
Insert(root->left, m, n);
}
else
{
Insert(root->left, m, mid);
Insert(root->right, mid, n);
}
}
统计线段树中节点cover域为true的线段的总长度，并返回结果，问题得解：
int Count(SegmentTreeNode *root)
{
if(root->cover == true)
{
return root->b - root->a;
}
else
{
if(root->b - root->a == 1)
{
return 0;
}
else
{
return Count(root->left) + Count(root->right);
}
}
}
把上述问题稍作变换，就可以得到另一个问题2：
桌子上零散地放着若干个盒子，桌子的后方是一堵墙。问从桌子前方可以看到多少个盒子？假设人站得足够远。
分析一下可知：
可以这样来看这道题：x轴上有若干条不同线段，将它们依次染上不同的颜色，问最后能看到多少种不同的颜色？（后染的颜色会覆盖原先的颜色）
我们可以这样规定：x轴初始是颜色0，第一条线段染颜色1，第二条线段染颜色2，以此类推。
原先构造线段树的方法不再适用，但是我们可以通过修改线段树的cover域的定义，使得这道题也能用线段树来解。
那么我们来给线段树新增一个color域，color = -1表示该区间存在多种颜色的线段，color = 0表示该区间未被着色，color > 0表示该区间仅存在一种颜色。
然后我们修改我们的insert方法和统计方法来求解这个问题：
void ColorInsert(SegmentTreeNode *root, int l, int r, int color) //求解染色段数的问题。
{
if(root->color != color || root->cover == false) //假如插入的线段跟当前线段颜色相同，我们检查该线段是否被完全着色
{
if(root->b - root->a == 1)//假如线段区间长度为1，直接着色
{
root->color = color;
root->cover = true;
}
else
{
if(root->color == 0 || root->a == l && root->b == r)//如果区间未被着色，或者插入的线段能够完全覆盖区间，则区间直接着色
{
root->color = color;
if(root->a == l && root->b == r)
root->cover = true; //完全覆盖区间，将cover置为true
}
else
{
if(root->color != color) //如果区间已经着色，并且cover=flase，则更新color = -1表示区间存在多种颜色。
{
root->color = -1;
}
}
int mid = (root->a + root->b) >> 1; //递归的给子树着色。
if(l >= mid)
{
ColorInsert(root->right, l, r, color);
}
else if(r <= mid)
{
ColorInsert(root->left, l, r, color);
}
else
{
ColorInsert(root->right, mid, r, color);
ColorInsert(root->left, l, mid, color);
}
}
}
}
下面就是我们解决这个问题，用到的统计策略，当我们遇到区间的color大于0时，表示区间只有一种颜色，将区间的颜色值放入一个set，当color小于0，则递归的查找，线段树子树并且判断该颜色是否已经存在。最后返回set的size即可
void Color(SegmentTreeNode *root, set<int> &iset)
{
if(root->color == 0 || root == NULL)
{
return;
}
if(root->color > 0)
{
if(!iset.count(root->color))
{
iset.insert(root->color);
}
}
else
{
Color(root->left, iset);
Color(root->right, iset);
}
}
参考文章：http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html
http://blog.chinaunix.net/uid-27103408-id-3801001.html