C++线段树(Segment Tree）二：静态开点、区间修改

发布于：2025-09-13 ⋅ 阅读:(14) ⋅ 点赞:(0)

前言

C++算法与数据结构本博文代码打包下载
C++线段树(Segment Tree）一：正确性证明、模板及封装类及样例

静态开点

如果所有元素是连续的，则可以用向量代替二叉树。根节点的数据放到v[1]，如果一个节点的数据存储在v[i]，则它的左孩子存储在v[ i × 2 ] i\times2] i×2]和v[ i × 2 + 1 ] i\times2+1] i×2+1]。节约存储空间。层号从0开始，编号从1开始，第i层第一个节点的编号是 2 i 2^i 2i。

区间修改(懒修改)

枚举时最多 4 l o g N 4logN 4logN个节点，令这些节点组成的集合为ns。
性质一：如果 x ∈ n s x \in ns x∈ns，则x的父节点也 x ∈ n s x \in ns x∈ns。
如果x是叶子节点，则相关节点都已经更新。如果x不是叶子节点，x的所有后代（不包括x)都没有修改，我们将对x的修改缓存到m_record[x]。当需要枚举、查询、修改x的后代时，更新缓存。
增加两个回调接口：
更新树枝节点OnUpdateBranch。
合并缓存,OnUnionSet。当一个树枝节点多次修改时合并缓存。比如修改是增加，则多次修改的值，也相加。

	void UpdateNode(int iNode, int iSaveLeft, int iSaveRight, TSet value) {
		if (iSaveLeft == iSaveRight) {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(m_save[iNode], iSaveLeft, value);//叶子节点
		}
		else {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateBranch(m_save[iNode], iSaveLeft, iSaveRight, value);
			CRangSegmentTree<TSave, TSet>::m_call.OnUnionSet(m_record[iNode], value);
		}
	}

封装类

回调定义

template<class TSave, class TSet >
class ISegmentTreeCall
{
public:
	virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) = 0;
};

template<class TSave, class TSet >
class ISingleSegmentTreeCall : public ISegmentTreeCall<TSave,TSet>
{
public:
	virtual void OnUpdateLeaf(TSave& save, int iSaveIndex, const TSet& update) = 0;
};

template<class TSave, class TSet >
class IRangleSegmentTreeCall : public ISingleSegmentTreeCall<TSave, TSet>
{
public:
	virtual void OnUnionSet(TSet& oldBuff, const TSet& newBuff) = 0;
	virtual void OnUpdateBranch(TSave& save, int iLeftIndex, int iRightIndex, const TSet& update) = 0;
};

单点更新（静态开点、动态开点)

template<class TSave, class TSet >
class CSegmentTree {
public:
	CSegmentTree(ISegmentTreeCall<TSave, TSet>& call, TSave tDefault)
		:m_call(call), m_tDefault(tDefault) {}
	TSave Query(int left, int r) {
		return Query(left, r, m_tDefault);
	}
	TSave Query(int left, int r,TSave tDefault) {
		TSave ans = tDefault;
		std::function<void(const TSave&, const int&, const int&)> fun = [&](const TSave& cur, const int& leftIndex, const int& rIndex) {
			m_call.OnUnion(ans, ans, cur, left, leftIndex - 1, rIndex);
		};
		Enum(left, r, fun);
		return ans;
	}
	virtual void Enum(int leftIndex, int leftRight, std::function<void(const TSave&, const int&, const int&)>& fun) = 0;	
	virtual TSave QueryAll() = 0;
protected:
	ISegmentTreeCall<TSave, TSet>& m_call;
	const TSave m_tDefault;
};
template<class TSave, class TSet >
class CSingeSegmentTree:public CSegmentTree<TSave,TSet>
{
public:
	CSingeSegmentTree(ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault)
		:m_call(call), CSegmentTree<TSave, TSet>(call,tDefault) {}
	virtual void Update(int index, TSet update) = 0;
protected:
	ISingleSegmentTreeCall<TSave, TSet>& m_call;
};
template<class TSave, class TSet >
class CSingeTreeSegmentTree : public CSingeSegmentTree<TSave, TSet>
{
protected:
	struct CTreeNode
	{
		TSave data;
		CTreeNode* m_lChild = nullptr, * m_rChild = nullptr;
		~CTreeNode() {
			delete m_lChild; m_lChild = nullptr;
			delete m_rChild; m_rChild = nullptr;
		}
	};
	CTreeNode* m_root;
	const int m_iMinIndex, m_iMaxIndex;
public:
	CSingeTreeSegmentTree(int iMinIndex, int iMaxIndex, ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault) :CSingeSegmentTree<TSave, TSet>(call, tDefault) 
	,m_iMinIndex(iMinIndex),m_iMaxIndex(iMaxIndex){
		m_root = CreateNode();
	}
	void Update(int index, TSet update) override {
		if ((index < m_iMinIndex) || (index > m_iMaxIndex)) { return; }
		Update(m_root,m_iMinIndex,m_iMaxIndex, index, update);
	}
	TSave QueryAll() override{
		return m_root->data;
	}
	//void OnQuery(TSave& ans, const TSave& cur, const int& iSaveLeft, const int& iSaveRight);
	void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun)override {
		if (max(iQueryLeft, m_iMinIndex) > min(iQueryRight, m_iMaxIndex)) { return; }//和根节点没交集
		Enum(m_root,m_iMinIndex,m_iMaxIndex, iQueryLeft, iQueryRight, fun);
	}
	~CSingeTreeSegmentTree() {
		delete m_root;
	}
protected:
	void Enum(CTreeNode* node,int iSaveLeft,int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
		if ((iQueryLeft<= iSaveLeft) && (iSaveRight <= iQueryRight)) {
			fun(node->data, iSaveLeft, iSaveRight);
			return;
		}
		CreateChilds(node);
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (mid >= iQueryLeft) {
			Enum(node->m_lChild,iSaveLeft,mid ,iQueryLeft, iQueryRight, fun);
		}
		if (mid + 1 <= iQueryRight) {
			Enum(node->m_rChild,mid+1,iSaveRight, iQueryLeft, iQueryRight, fun);
		}
	}
	void Update(CTreeNode* node, int iSaveLeft, int iSaveRight, int iUpdateNO, TSet update) {
		if (iSaveLeft == iSaveRight) {
			m_call.OnUpdateLeaf(node->data, iUpdateNO, update);
			return;
		}
		CreateChilds(node);
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (iUpdateNO <= mid)
		{
			Update(node->m_lChild,iSaveLeft,mid, iUpdateNO, update);
		}
		else {
			Update(node->m_rChild, mid+1, iSaveRight, iUpdateNO, update);
		}
		m_call.OnUnion(node->data, node->m_lChild->data, node->m_rChild->data, iSaveLeft,mid, iSaveRight);
	}
	CTreeNode* CreateNode() {
		CTreeNode* node = new CTreeNode;
		node->data = this->m_tDefault;
		return node;
	}
	void CreateChilds(CTreeNode* node) {
		if (nullptr != node->m_lChild) { return; }
		node->m_lChild = CreateNode();
		node->m_rChild = CreateNode();
	}
};

template<class TSave, class TSet >
class CSingleVectorSegmentTree : public CSingeSegmentTree<TSave, TSet>
{
public:
	CSingleVectorSegmentTree(int iEleSize, ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault) :
		m_iEleSize(iEleSize), CSingeSegmentTree<TSave, TSet>(call, tDefault), m_save(iEleSize * 4, tDefault) {

	}
	void Update(int index, TSet update) override {
		if ((index < 0) || (index >= m_iEleSize)) { return; }
		Update(1, 0, m_iEleSize - 1, index, update);
	}
	TSave QueryAll() override {
		return m_save[1];
	}
	virtual void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) override {
		if (max(iQueryLeft, 0) > min(iQueryRight, m_iEleSize - 1)) { return; }//和根节点没交集
		Enum(1, 0, m_iEleSize - 1, iQueryLeft, iQueryRight, fun);
	}
	void swap(CSingleVectorSegmentTree& o) {
		m_save.swap(o.m_save);
	}
protected:
	const int m_iEleSize;
	/*	void Init(std::function<void(TSave&, const int&)> fun, int iNodeNO, int iSaveLeft, int iSaveRight)
		{
			if (iSaveLeft == iSaveRight) {
				fun(m_save[iNodeNO], iSaveLeft);
				return;
			}
			const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
			Init(fun, iNodeNO * 2, iSaveLeft, mid);
			Init(fun, iNodeNO * 2 + 1, mid + 1, iSaveRight);
			this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
		}*/
	void Enum(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
		if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
			fun(m_save[iNodeNO], iSaveLeft, iSaveRight);
			return;
		}
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (mid >= iQueryLeft) {
			Enum(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight, fun);
		}
		if (mid + 1 <= iQueryRight) {
			Enum(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight, fun);
		}
	}
	void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TSet update) {
		if (iSaveLeft == iSaveRight)
		{
			CSingeSegmentTree<TSave,TSet>::m_call.OnUpdateLeaf(m_save[iNodeNO], iSaveLeft, update);
			return;
		}
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (iUpdateNO <= mid) {
			Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
		}
		else {
			Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
		}
		CSegmentTree<TSave, TSet>::m_call.OnUnion(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, mid, iSaveRight);
	}
	vector<TSave> m_save;
};

区间更新（静态开点、动态开点)



template<class TSave, class TSet >
class CRangSegmentTree :public CSegmentTree<TSave, TSet>
{
public:
	CRangSegmentTree(IRangleSegmentTreeCall<TSave, TSet>& call, TSave tDefault, TSet tRecordNull)
		:m_call(call), CSegmentTree<TSave, TSet>(call, tDefault), m_recordNull(tRecordNull){}
	virtual void Update(int iLeftIndex, int iRightIndex, TSet value) = 0;
protected:
	IRangleSegmentTreeCall<TSave, TSet>& m_call;
	TSet m_recordNull;
};

template<class TSave, class TSet >
class CRangeVectorSegmentTree : public CRangSegmentTree<TSave, TSet>
{
public:
	CRangeVectorSegmentTree(int iEleSize, IRangleSegmentTreeCall<TSave, TSet>& call, TSave tDefault, TSet tRecordNull) :m_iEleSize(iEleSize), CRangSegmentTree<TSave, TSet>(call, tDefault, tRecordNull)
		, m_save(iEleSize * 4, tDefault), m_record(iEleSize * 4, tRecordNull) {
		CRangSegmentTree<TSave, TSet>::m_recordNull = tRecordNull;
	}
	virtual void Update(int iLeftIndex, int iRightIndex, TSet value) override
	{
		if (max(iLeftIndex, 0) > min(iRightIndex, m_iEleSize - 1)) { return; }//和根节点没交集
		Update(1, 0, m_iEleSize - 1, iLeftIndex, iRightIndex, value);
	}
	virtual void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) override {
		if (max(iQueryLeft, 0) > min(iQueryRight, m_iEleSize - 1)) { return; }//和根节点没交集
		Enum(1, 0, m_iEleSize - 1, iQueryLeft, iQueryRight, fun);
	}
	//void Init() {
	//	Init(1, 0, m_iEleSize - 1);
	//}
	TSave QueryAll() override {
		return m_save[1];
	}
	void swap(CRangeVectorSegmentTree<TSave, TSet>& other) {
		m_save.swap(other.m_save);
		m_record.swap(other.m_record);
		std::swap(CRangSegmentTree<TSave, TSet>::m_recordNull, other.m_recordNull);
		std::swap(CSegmentTree<TSave, TSet>::m_tDefault, other.m_tDefault);
		assert(m_iEleSize == other.m_iEleSize);
	}
protected:
	//void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
	//{
	//	if (iSaveLeft == iSaveRight) {
	//		this->OnInit(m_save[iNodeNO], iSaveLeft);
	//		return;
	//	}
	//	const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
	//	Init(iNodeNO * 2, iSaveLeft, mid);
	//	Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
	//	this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
	//}
	void Enum(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
		if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
			fun(m_save[iNodeNO], iSaveLeft, iSaveRight);
			return;
		}
		FreshChild(iNodeNO, iSaveLeft, iSaveRight);
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (mid >= iQueryLeft) {
			Enum(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight, fun);
		}
		if (mid + 1 <= iQueryRight) {
			Enum(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight, fun);
		}
	}
	void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TSet value)
	{
		if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
		{
			UpdateNode(iNode, iSaveLeft, iSaveRight, value);
			return;
		}
		if (iSaveLeft == iSaveRight) {
			return;//没有子节点
		}
		FreshChild(iNode, iSaveLeft, iSaveRight);
		const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (iMid >= iOpeLeft)
		{
			Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);
		}
		if (iMid + 1 <= iOpeRight)
		{
			Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);
		}
		// 如果有后代，至少两个后代
		CRangSegmentTree<TSave, TSet>::m_call.OnUnion(m_save[iNode], m_save[iNode * 2], m_save[iNode * 2 + 1], iSaveLeft, iMid, iSaveRight);
	}
	void UpdateNode(int iNode, int iSaveLeft, int iSaveRight, TSet value) {
		if (iSaveLeft == iSaveRight) {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(m_save[iNode], iSaveLeft, value);//叶子节点
		}
		else {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateBranch(m_save[iNode], iSaveLeft, iSaveRight, value);
			CRangSegmentTree<TSave, TSet>::m_call.OnUnionSet(m_record[iNode], value);
		}
	}
	void FreshChild(int iNode, int iDataLeft, int iDataRight)
	{
		if (CRangSegmentTree<TSave, TSet>::m_recordNull == m_record[iNode])
		{
			return;
		}
		const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
		UpdateNode(iNode * 2, iDataLeft, iMid, m_record[iNode]);
		UpdateNode(iNode * 2 + 1, iMid + 1, iDataRight, m_record[iNode]);
		m_record[iNode] = CRangSegmentTree<TSave, TSet>::m_recordNull;
	}
	vector<TSave> m_save;
	vector<TSet> m_record;
	const int m_iEleSize;
};

template<class TSave, class TSet >
class CRangeTreeSegmentTree : public CRangSegmentTree<TSave, TSet>
{
public:
	CRangeTreeSegmentTree(int iMinIndex, int iMaxIndex, IRangleSegmentTreeCall<TSave, TSet>& call, TSave tDefault, TSet tRecordDef) :
		CRangSegmentTree<TSave, TSet>(call, tDefault, tRecordDef),m_iMinIndex(iMinIndex),m_iMaxIndex(iMaxIndex)
	{
		m_root = CreateNode();
	}
	virtual void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) override {
		if (max(iQueryLeft, m_iMinIndex) > min(iQueryRight, m_iMaxIndex)) { return; }//和根节点没交集
		Enum(m_root, m_iMinIndex, m_iMaxIndex, iQueryLeft, iQueryRight, fun);
	}
	virtual void Update(int iLeftIndex, int iRightIndex, TSet value) override
	{
		if (max(iLeftIndex, m_iMinIndex) > min(iRightIndex, m_iMaxIndex)) { return; }//和根节点没交集
		Update(m_root, m_iMinIndex, m_iMaxIndex, iLeftIndex, iRightIndex, value);
	}
	TSave QueryAll() override {
		return m_root->data;
	}
protected:
	struct CTreeNode
	{
		TSet record;
		TSave data;
		CTreeNode* m_lChild = nullptr, * m_rChild = nullptr;
	};
	CTreeNode* m_root;
	const int m_iMinIndex, m_iMaxIndex;
	void CreateChilds(CTreeNode* node) {
		if (nullptr != node->m_lChild) { return; }
		node->m_lChild = CreateNode();
		node->m_rChild = CreateNode();
	}
	CTreeNode* CreateNode() {
		CTreeNode* node = new CTreeNode;
		node->data = CSegmentTree<TSave, TSet>::m_tDefault;
		node->record = CRangSegmentTree<TSave, TSet>::m_recordNull;
		return node;
	}
	void UpdateNode(CTreeNode* node, int iSaveLeft, int iSaveRight, TSet value) {
		if (iSaveLeft == iSaveRight) {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(node->data, iSaveLeft, value);//叶子节点
		}
		else {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateBranch(node->data, iSaveLeft, iSaveRight, value);
			CRangSegmentTree<TSave, TSet>::m_call.OnUnionSet(node->record, value);
		}
	}
	void FreshChild(CTreeNode* node,int left,int mid,int right)
	{
		if (CRangSegmentTree<TSave, TSet>::m_recordNull == node->record)
		{
			return;
		}
		CreateChilds(node);
		UpdateNode(node->m_lChild, left,mid,node->record);
		UpdateNode(node->m_rChild,mid+1,right, node->record);
		node->record = CRangSegmentTree<TSave, TSet>::m_recordNull;
	}
	void Update(CTreeNode* node,int iSaveLeft, int iSaveRight,int iOpeLeft, int iOpeRight, TSet value)
	{
		if ((iOpeLeft <= iSaveLeft) && (iSaveRight <= iOpeRight)) {
			UpdateNode(node,iSaveLeft,iSaveRight, value);
			return;
		}
		CreateChilds(node);		
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		FreshChild(node,iSaveLeft,mid,iSaveRight);
		if (mid >= iOpeLeft)
		{
			Update(node->m_lChild,iSaveLeft,mid, iOpeLeft, iOpeRight, value);
		}
		if (mid + 1 <= iOpeRight)
		{
			Update(node->m_rChild,mid+1,iSaveRight, iOpeLeft, iOpeRight, value);
		}
		// 如果有后代，至少两个后代
		CRangSegmentTree<TSave, TSet>::m_call.OnUnion(node->data, node->m_lChild->data, node->m_rChild->data, iSaveLeft, mid, iSaveRight);
	}
	void Enum(CTreeNode* node, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
		if ((iQueryLeft <= iSaveLeft) && (iSaveRight <= iQueryRight)) {
			fun(node->data, iSaveLeft, iSaveRight);
			return;
		}
		CreateChilds(node);
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		FreshChild(node,iSaveLeft,mid,iSaveRight);		
		if (mid >= iQueryLeft) {
			Enum(node->m_lChild,iSaveLeft,mid, iQueryLeft, iQueryRight, fun);
		}
		if (mid + 1 <= iQueryRight) {
			Enum(node->m_rChild,mid+1,iSaveRight, iQueryLeft, iQueryRight, fun);
		}
	}
};

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

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

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布