手把手写线段树

2021-11-03   


手把手写线段树

题目分析

这道题, 无非就是一段时间可用或者是不可用, 很理所当然的, 我们就可以联想到使用线段树来解决这题

而线段树所具有的属性了就应该是, 这一段时间是否是可用的, 我们可以以此定义一个bool类型的成员

bool available = true;

写一下完整的树的结点:

class TreeNode
{
public:
    	// 树的成员
    	TreeNode* left;
    	TreeNode* right;
    	// 线段树特殊的
    	bool available = true;
    	bool lazy = true;
};

创建线段树

接下来 我们就用上面讲的三步走的方法来书写创建线段树的递归

首先, 对于一颗这样的线段树
在这里插入图片描述
来试着创建这棵线段树

1. 首先给这个函数下定义

TreeNode* build(int beg, int end);

定义build函数: 创建一颗线段树, 其的根节点的范围就是[beg, end], 返回这棵线段树的root节点

下完了这个定义, 那我们的build函数就具有了我们下过定义的这个作用!

2. 分析做什么?

以下的三件事:

  • 生成根节点, 要把它的范围设置为 [beg ,end]

    TreeNode* root = new TreeNode();
    
    root->beg = beg;
    root->end = end;
    
  • 构造左子树, 其范围为[beg, mid]

    //创建一颗线段树, 其的根节点的范围就是[beg, mid], 返回这棵线段树的root节点
    root->left = build(beg, mid);
    
  • 构造右子树, 其范围为[mid + 1, end]

    root->right = build(mid + 1, end);
    
  • 不难看出 我们的mid可以取

    int mid = (beg + end) / 2;
    

3. 什么时候来做

让我们来看看2中分析的三个步骤

不管这三个步骤的顺序是如何, 只要这三个步骤有执行, 手把手这棵线段树就可以生成啊

结果都是一样的

所以 随便!随便!

我们这个函数的大概轮廓就出来了

TreeNode* build(int beg, int end)
{
    TreeNode* root = new TreeNode();

	root->beg = beg;
	root->end = end;
    
    // 处理一下边界条件
    // xxxxx
        
    int mid = (beg + end) / 2;
    root->left = build(beg, mid);
    root->right = build(mid + 1, end);
}

* 最后, 加小料

  • 边界条件

     beg == end;
    
    if(beg == end)
    {
        return root;
    }
    
  • 返回值

    return root;
    

代码示例

@brief 构建一棵线段树 并且返回其root
TreeNode* build(int beg, int end)
{
    TreeNode* root = new TreeNode();

	root->beg = beg;
	root->end = end;
    
	if(beg == end)
	{
    	return root;
	}
        
    int mid = (beg + end) / 2;
    root->left = build(beg, mid);
    root->right = build(mid + 1, end);
    
    return root;
}

修改线段树

对于本道题来说, 会议成功预约, 其实就是将一段时间设为不可, TreeNode::available = false

三步走:

1. 给函数下定义

定义函数setTree : 将以root为根节点的这棵线段树上的一段时间[beg, end]的available 设为false

TreeNode* setTree(TreeNode* root, int beg, int end, bool avaliable);

2. 做什么?

在这里插入图片描述

假设我们要修改[beg ,end]

  • 首先, 我们要修正区间范围, 比如, [beg, end] == [3, 10], 需要将区间修正为[3, 5]

    beg = beg < root->beg ? root->beg : beg;
    end = end > root->end ? root->end : end;
    
  • 比如, [beg, end] == [0, 5], 这时候 root节点的区间是不是就是我们需要修改的区间啊, 这时候, 我们就可以修改这个区间上的值了

    if(beg == root->beg && end == root->end)
    {
        root->available = avaliable;
        root->lazy = avaliable;
        
        return root;
    }
    
  • 比如, [beg, end] == [6, 10], 这个区间和root节点的区间, 退

    被修正完以后 就变成了[6, 5]

    if(beg > end)
    {
        return root;
    }
    
  • 比如, [beg, end] == [3, 5], 我们需要在这棵树的左右子线段树中, 对这段时间进行修改

    root->left = setTree(root->left, beg, end, available);
    root->right = setTree(root->right, beg, end, available);
    root->available = false;
    return root;
    

3. 什么时候做

看我们在2中的分析

TreeNode* setTree(TreeNode* root, int beg, int end, bool avaliable)
{
    beg = beg < root->beg ? root->beg : beg;
	end = end > root->end ? root->end : end;
    
    if(beg == root->beg && end == root->end)
    {
        root->available = avaliable;
        root->lazy = avaliable;

        return root;
    }
    
    if(beg > end)
    {
        return root;
    }
    
    root->left = setTree(root->left, beg, end, available);
    root->right = setTree(root->right, beg, end, available);
    root->available = false;
    return root;
}

* 小料 边界条件

不难看出, 当

root == nullptr

边界处理

if(root == nullptr)
{
    return nullptr;
}

代码示例

TreeNode* setTree(TreeNode* root, int beg, int end, bool avaliable)
{
    if(root == nullptr)
    {
        return nullptr;
    }
    
    beg = beg < root->beg ? root->beg : beg;
	end = end > root->end ? root->end : end;
    
    if(beg == root->beg && end == root->end)
    {
        root->available = avaliable;
        root->lazy = avaliable;

        return root;
    }
    
    if(beg > end)
    {
        return root;
    }
    
    root->left = setTree(root->left, beg, end, available);
    root->right = setTree(root->right, beg, end, available);
    root->available = false;
    return root;
}

下传懒惰标签 pushDown()

在这里插入图片描述

当懒惰标签的值为false的时候, 是不是应该下传懒惰标签, 让他的子节点的available值都变为false, 并且重置懒惰标签

1. 给函数下定义

下传值为false的lazy

定义一个函数pushDown: 下传false的懒惰标签, 并重置当前的懒惰标签为true, 返回修改后的root节点

TreeNode* pushDown(TreeNode *root);

2. 做什么?

  • 当前节点的available值是不是应该改为false

    root->available = false;
    
  • 重置当前的lazy为true

    root->lazy = true;
    
  • 将懒惰标签向当前节点的左右子树取传递

    root->left = pushDown(root->left);
    root->right = pushDown(root->right);
    

3. 什么时候做?

这三件事由顺序吗?!!

谁先谁后都没毛病啊

TreeNode* pushDown(TreeNode *root)
{
    root->available = false;
    
	root->lazy = true;
    
    root->left = pushDown(root->left);
	root->right = pushDown(root->right);
    
    return root;
}

*小料 边界条件

很容易可以得到

root == nullptr

这个函数就可以退出了

if(root == nullptr)
{
    return nullptr;
}

代码示例

TreeNode* pushDown(TreeNode *root)
{
    if(root == nullptr)
	{
    	return nullptr;
	}
    
    root->available = false;
    
	root->lazy = true;
    
    root->left = pushDown(root->left);
	root->right = pushDown(root->right);
    
    return root;
}

获得一段时间的值

bool getTree(TreeNode* root, int beg, int end)
{
    if(root == nullptr)
    {
        return nullptr;
    }
    
    // 下传lazy
    if(!root->lazy)
    {
        pushDown(root);
    }
    
    beg = beg < root->beg ? root->beg : beg;
	end = end > root->end ? root->end : end;
    
    if(beg == root->beg && end == root->end)
    {
        return root->available;
    }
    
    if(beg > end)
    {
        return true;
    }
    
    return getTree(root->left, beg, end) && getTree(root->right, beg, end);
}

最终代码

#include <iostream>
#include <cstdio>

using namespace std;

class TreeNode
{
public:
    int beg;
    int end;
    TreeNode *left;
    TreeNode *right;
    bool available = true;
    bool lazy = true;
};

inline void bfs(TreeNode *root)
{
    if (root == nullptr)
    {
        return;
    }
    printf("(%d, %d) ailable = %d lazy = %d\t\n", root->beg, root->end, root->available, root->lazy);
    bfs(root->left);
    bfs(root->right);
}

inline TreeNode *buildTree(int beg, int end)
{
    if (beg > end)
    {
        return nullptr;
    }

    TreeNode *res = new TreeNode();
    if (beg == end)
    {
        res->beg = beg;
        res->end = beg;
        return res;
    }

    int mid = (beg + end) / 2;
    res->left = buildTree(beg, mid);
    res->right = buildTree(mid + 1, end);

    // 后序位置
    res->beg = beg;
    res->end = end;

    return res;
}

inline TreeNode *setTree(TreeNode *root, int beg, int end, bool available)
{
    if (root == nullptr)
    {
        return nullptr;
    }

    // 截断区间
    beg = beg < root->beg ? root->beg : beg;
    end = end > root->end ? root->end : end;

    // 区间完全不被包含
    if (beg > end)
    {
        return root;
    }
    // 区间完全被包含
    if (beg == root->beg && end == root->end)
    {
        // 区间修改
        root->available = available;
        root->lazy = available;
        return root;
    }
    // 区间被包含
    root->left = setTree(root->left, beg, end, available);
    root->right = setTree(root->right, beg, end, available);
    root->available = available;
    return root;
}

inline TreeNode* pushDown(TreeNode *root)
{
    if(root == nullptr)
	{
    	return nullptr;
	}
    
    root->available = false;
    
	root->lazy = true;
    
    root->left = pushDown(root->left);
	root->right = pushDown(root->right);
    
    return root;
}

inline bool getTree(TreeNode* root, int beg, int end)
{
    if(root == nullptr)
    {
        return false;
    }
    
    // 下传lazy
    if(!root->lazy)
    {
        pushDown(root);
    }
    
    beg = beg < root->beg ? root->beg : beg;
	end = end > root->end ? root->end : end;
    
    if(beg == root->beg && end == root->end)
    {
        return root->available;
    }
    
    if(beg > end)
    {
        return true;
    }
    
    return getTree(root->left, beg, end) && getTree(root->right, beg, end);
}

int main()
{
    int n;
    int m;

    scanf("%d %d", &n, &m);

    TreeNode *root = buildTree(1, m);

    for (auto i = 0; i != n; ++i)
    {
        int beg;
        int end;

        scanf("%d %d", &beg, &end);

        // 判断时候可以预约
        if (getTree(root, beg, end))
        {
            printf("ACCEPTED\n");
            // 设置不可用
            setTree(root, beg, end, false);
        }
        else
        {
            printf("REJECTED\n");
        }
    }
    return 0;
}

Q.E.D.