【线段树】2276. 统计区间中的整数数目

算法可以发掘本质，如：
一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。
三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。
四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。
一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。 而这三者是等效问题。

本文涉及知识点

线段树

LeetCode2276. 统计区间中的整数数目

给你区间的 空 集，请你设计并实现满足要求的数据结构：
新增：添加一个区间到这个区间集合中。
统计：计算出现在 至少一个 区间中的整数个数。
实现 CountIntervals 类：
CountIntervals() 使用区间的空集初始化对象
void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
int count() 返回出现在 至少一个 区间中的整数个数。
注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。
示例 1：
输入
[“CountIntervals”, “add”, “add”, “count”, “add”, “count”]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]
解释
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count(); // 返回 6
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中
countIntervals.count(); // 返回 8
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 5 和 6 出现在区间 [5, 8] 中
// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
// 整数 9 和 10 出现在区间 [7, 10] 中
提示：
1 <= left <= right <= 109
最多调用 add 和 count 方法 总计 105 次
调用 count 方法至少一次

线段树

由于本题无法离散化，所以用数组内存必定会超，只能用哈希映射或二叉树动态开点，二叉树的性能略好，就用二叉树。就算用二叉树也刚刚能过。
区间修改，查询全部。
由于只用到了查询全部，所以查询可以不实现。
save 记录 整个区间 在题目所在区间的数量。
叶子save 的值为1，表示在至少一个区间。0，表示不在任何区间。

template<class TSave=int, class TRecord =int >
class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord>
{	
public:
	using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree;
protected:
	virtual void OnQuery(TSave& save) override
	{
	}
	virtual void OnUpdate(TSave& save, int iSaveLeft, int iSaveRight, const TRecord& update) override
	{ 
		save = update*(iSaveRight-iSaveLeft+1);
	}
	virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
	{
		par = left + r;
	}
	virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
	{
		old = newRecord;
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

本题只会更新1，如果需要考虑取消，也就是更新为0。需要将懒标记的默认值设置成-1。
CountIntervals():m_treeLine(1,1’000’000’000,0,-1){

}
  • 1

代码

template<class TSave, class TRecord >
class CRangUpdateLineTree 
{
protected:
	virtual void OnQuery(TSave& save) = 0;
	virtual void OnUpdate(TSave& save, int iSaveLeft,int iSaveRight, const TRecord& update) = 0;
	virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
	virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
};


template<class TSave, class TRecord >
class CTreeRangeLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
protected:
	struct CTreeNode
	{
		int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; }
		int m_iMinIndex;
		int m_iMaxIndex;
		TRecord record;
		TSave data;
		CTreeNode* m_lChild = nullptr, * m_rChild = nullptr;
	};
	CTreeNode* m_root;
	TSave m_tDefault;
	TRecord m_tRecordDef;
public:
	CTreeRangeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault,TRecord tRecordDef) {
		m_tDefault = tDefault;
		m_tRecordDef = tRecordDef;
		m_root = CreateNode(iMinIndex, iMaxIndex);
	}
	void Update(int iLeftIndex, int iRightIndex, TRecord value)
	{
		Update(m_root, iLeftIndex, iRightIndex, value);
	}
	TSave QueryAll() {
		return m_root->data;
	}
	void Query(int leftIndex, int leftRight) {
		Query(m_root, leftIndex, leftRight);
	}
protected:
	void Query(CTreeNode* node, int iQueryLeft, int iQueryRight) {
		if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) {
			this->OnQuery(node->data);
			return;
		}
		if (1 == node->Cnt()) {//没有子节点
			return;
		}
		CreateChilds(node);
		Fresh(node);
		const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
		if (mid >= iQueryLeft) {
			Query(node->m_lChild, iQueryLeft, iQueryRight);
		}
		if (mid + 1 <= iQueryRight) {
			Query(node->m_rChild, iQueryLeft, iQueryRight);
		}
	}
	void Update(CTreeNode* node, int iOpeLeft, int iOpeRight, TRecord value)
	{
		const int& iSaveLeft = node->m_iMinIndex;
		const int& iSaveRight = node->m_iMaxIndex;
		if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
		{
			this->OnUpdate(node->data, iSaveLeft, iSaveRight, value);
			this->OnUpdateRecord(node->record, value);
			return;
		}
		if (1 == node->Cnt()) {//没有子节点
			return;
		}
		CreateChilds(node);
		Fresh(node);
		const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
		if (mid >= iOpeLeft) {
			this->Update(node->m_lChild, iOpeLeft, iOpeRight, value);
		}
		if (mid + 1 <= iOpeRight) {
			this->Update(node->m_rChild, iOpeLeft, iOpeRight, value);
		}
		// 如果有后代，至少两个后代
		this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data,node->m_iMinIndex,node->m_iMaxIndex);
	}
	void CreateChilds(CTreeNode* node) {
		if (nullptr != node->m_lChild) { return; }
		const int iSaveLeft = node->m_iMinIndex;
		const int iSaveRight = node->m_iMaxIndex;
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		node->m_lChild = CreateNode(iSaveLeft, mid);
		node->m_rChild = CreateNode(mid + 1, iSaveRight);
	}
	CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) {
		CTreeNode* node = new CTreeNode;
		node->m_iMinIndex = iMinIndex;
		node->m_iMaxIndex = iMaxIndex;
		node->data = m_tDefault;
		node->record = m_tRecordDef;
		return node;
	}
	void Fresh(CTreeNode* node)
	{
		if (m_tRecordDef == node->record)
		{
			return;
		}
		CreateChilds(node);
		Update(node->m_lChild, node->m_lChild->m_iMinIndex, node->m_lChild->m_iMaxIndex, node->record);
		Update(node->m_rChild, node->m_rChild->m_iMinIndex, node->m_rChild->m_iMaxIndex, node->record);
		node->record = m_tRecordDef;
	}
};

template<class TSave=int, class TRecord =int >
class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord>
{	
public:
	using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree;
protected:
	virtual void OnQuery(TSave& save) override
	{
	}
	virtual void OnUpdate(TSave& save, int iSaveLeft, int iSaveRight, const TRecord& update) override
	{ 
		save = update*(iSaveRight-iSaveLeft+1);
	}
	virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
	{
		par = left + r;
	}
	virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
	{
		old = newRecord;
	}
};

class CountIntervals {
public:
	CountIntervals():m_treeLine(1,1'000'000'000,0,0){
	}
	void add(int left, int right) {
		m_treeLine.Update(left, right,1);
	}
	int count() {
		return m_treeLine.QueryAll();
	}
	CMyTreeRangeLineTree<> m_treeLine;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151

测试用例

CountIntervals countIntervals ; // 用一个区间空集初始化对象
	countIntervals.add(2, 3);  // 将 [2, 3] 添加到区间集合中
	countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
	auto res = countIntervals.count();    // 返回 6
							   // 整数 2 和 3 出现在区间 [2, 3] 中
							   // 整数 7、8、9、10 出现在区间 [7, 10] 中
	Assert(6, res);
	countIntervals.add(5, 8);  // 将 [5, 8] 添加到区间集合中
	 res = countIntervals.count();    // 返回 8
							   // 整数 2 和 3 出现在区间 [2, 3] 中
							   // 整数 5 和 6 出现在区间 [5, 8] 中
							   // 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
							   // 整数 9 和 10 出现在区间 [7, 10] 中
	 Assert(8, res);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/137265314"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！