首页 > 代码库 > 线段树的实现及其经典用法（C++实现）

线段树的实现及其经典用法（C++实现）

2024-08-04 10:35:39   224人阅读

    一、线段树的定义

    首先，线段树是一棵完全二叉树。它的特点是：每个结点表示的是一个线段，或者说是一个区间。事实上，一棵线段树的根结点表示的是“整体”区间，而它的左右子树也是一棵线段树，分别表示区间的左半边和右半边。树中的每个结点表示一个区间[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





线段树的实现及其经典用法（C++实现）


联系
我们