信金在线制作网站,电子宣传册制作app,c2c网站代表,上海人才市场档案存放中心线段树是一种二叉搜索树#xff0c;与区间树相似#xff0c;它将一个区间划分成一些单元区间#xff0c;每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数#xff0c;时间复杂度为O(logN)。而未优化的空间复杂度为2N与区间树相似它将一个区间划分成一些单元区间每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数时间复杂度为O(logN)。而未优化的空间复杂度为2N实际应用时一般还要开4N的数组以免越界因此有时需要离散化让空间压缩。 区间更新查询的时间复杂度是O(logn)使用懒惰法只会影响以下四类节点每类节点数量都不超过logn。一左边界及其祖先。二右边界及其祖先。三第一类的兄弟节点。四第二类的兄弟节点。 本封装类都是使用数组模拟如果不是连续的节点需要离散化。如果是流无法离散化。则需要用哈希映射或树。
封装类
单点初始化、更新
templateclass TSave,class TRecord
class CSingUpdateLineTree
{
public:CSingUpdateLineTree(int iEleSize):m_iEleSize(iEleSize), m_vSave(iEleSize*4){}void Update(int index, TRecord update) {Update(1, 1, m_iEleSize, index 1, update);}void Query(int leftIndex, int leftRight) {Query(1, 1, m_iEleSize, leftIndex 1, leftRight 1);}void Init() {Init(1, 1, m_iEleSize);}const int m_iEleSize;
protected:void Init(int iNodeNO, int iSaveLeft, int iSaveRight){if (iSaveLeft iSaveRight) {OnInit(m_vSave[iNodeNO], iSaveLeft);return;}const int mid iSaveLeft (iSaveRight - iSaveLeft) / 2;Init(iNodeNO * 2, iSaveLeft, mid);Init(iNodeNO * 21, mid1, iSaveRight);OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2 1], iSaveLeft, iSaveRight);}void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft,int iQueryRight) {if (( iSaveLeft iQueryLeft) (iSaveRight iQueryRight )) {OnQuery(m_vSave[iNodeNO]);return;}if (iSaveLeft iSaveRight) {//没有子节点return;}const int mid iSaveLeft (iSaveRight - iSaveLeft) / 2;if (mid iQueryLeft) {Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);}if( mid1 iQueryRight ){Query(iNodeNO * 21, mid1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNodeNO,int iSaveLeft,int iSaveRight,int iUpdateNO, TRecord update) {if (iSaveLeft iSaveRight){OnUpdate(m_vSave[iNodeNO], update);return;}const int mid iSaveLeft (iSaveRight - iSaveLeft) / 2;if (iUpdateNO mid) {Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);}else {Update(iNodeNO * 21, mid1, iSaveRight, iUpdateNO, update);}OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 21],iSaveLeft,iSaveRight);}virtual void OnInit(TSave save,int iSave)0;virtual void OnQuery(TSave save) 0;virtual void OnUpdate(TSave save, const TRecord update) 0;virtual void OnUpdateParent(TSave par, const TSave left, const TSave r,int iSaveLeft,int iSaveRight) 0;vectorTSave m_vSave;
};区间更新、区间查询
templateclass TSave, class TRecord
class CLineTree
{
public:CLineTree(int iEleSize, TRecord recordNull0):m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4), m_vRecord(m_iEleSize * 4, recordNull), m_recordNull(recordNull){}void Update(int iLeftIndex, int iRightIndex, TRecord value){Update(1, 1, m_iEleSize, iLeftIndex 1, iRightIndex 1, value);}void Query( int iLeftIndex, int iRightIndex){Query( 1, 1, m_iEleSize, iLeftIndex 1, iRightIndex 1);}
private:virtual void OnQuery(TSave save) 0;virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) 0;virtual void OnUpdateParent(TSave par, const TSave left, const TSave r) 0;virtual void OnUpdate(TSave save, const int len, const TRecord update) 0;void Query( int iNode, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight){if ((iQueryLeft iSaveLeft) (iQueryRight iSaveRight)){OnQuery(m_vArr[iNode]);return;}Fresh(iNode, iSaveLeft, iSaveRight);const int iMid iSaveLeft (iSaveRight - iSaveLeft) / 2;if (iMid iQueryLeft){Query( iNode * 2, iSaveLeft, iMid, iQueryLeft, iQueryRight);}if (iMid 1 iQueryRight){Query( iNode * 2 1, iMid 1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value){if (iNode m_vArr.size()){return;}if ((iOpeLeft iSaveLeft) (iOpeRight iSaveRight)){OnUpdate(m_vArr[iNode], min(iSaveRight, iOpeRight) - max(iSaveLeft, iOpeLeft) 1, value);OnUpdateRecord(m_vRecord[iNode], value);return;}Fresh(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);}// 如果有后代至少两个后代OnUpdateParent(m_vArr[iNode], m_vArr[iNode * 2], m_vArr[iNode * 2 1]);}void Fresh(int iNode, int iDataLeft, int iDataRight){if (m_recordNull m_vRecord[iNode]){return;}const int iMid iDataLeft (iDataRight - iDataLeft) / 2;Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_vRecord[iNode]);Update(iNode * 2 1, iMid 1, iDataRight, iMid 1, iDataRight, m_vRecord[iNode]);m_vRecord[iNode] m_recordNull;}const int m_iEleSize;vectorTSave m_vArr;vectorTRecord m_vRecord;const TRecord m_recordNull;
};样例汇总
【线段树】【前缀和】1687从仓库到码头运输箱子
templateclass TSave int , class TRecord int
class CMinLineTree : public CLineTreeTSave, TRecord
{
public:using CLineTreeTSave, TRecord::CLineTree;int m_iQueryValue INT_MAX;
protected:virtual void OnQuery(TSave save) override{m_iQueryValue min(m_iQueryValue, save);}virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) override{old newRecord;}virtual void OnUpdateParent(TSave par, const TSave left, const TSave r) override{par min(left, r);}virtual void OnUpdate(TSave save, const int len, const TRecord update) override{save update;}};
【线段树】1622. 奇妙序列 templateclass TSave C1097Int, class TRecord pairC1097Int,C1097Int class CMyLineTree : public CLineTreeTSave, TRecord{public:using CLineTreeTSave, TRecord::CLineTree; protected:virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) override{old.first * newRecord.first;old.second old.second * newRecord.first newRecord.second;}virtual void OnUpdateParent(TSave par, const TSave left, const TSave r) override{}virtual void OnUpdate(TSave save, const int len, const TRecord iUpdate) override{save save * iUpdate.first iUpdate.second;}};【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票
templateclass TSave, class TRecord, TRecord RecordNull 0
class CMaxLineTree : public CLineTreeTSave, TRecord, RecordNull
{using CLineTree TSave, TRecord, RecordNull::CLineTree;virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) override{old newRecord;}virtual void OnUpdateParent(TSave par, const TSave left, const TSave r) override{par max(left, r);}virtual void OnUpdate(TSave save, const int len, const TRecord iUpdate) override{save iUpdate;}
};【线段树】【区间更新】2916. 子数组不同元素数目的平方和 II
class CPOW2LineTree : public CLineTreepairC1097Int, C1097Int,int
{
public:typedef pairC1097Int, C1097Int TSave;typedef int TRecord;const TRecord RecordNull 0 ;using CLineTree::CLineTree;// 通过 CLineTree 继承virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) override{old newRecord;}// 通过 CLineTree 继承virtual void OnUpdateParent(TSave par, const TSave left, const TSave r) override{par.first left.first r.first;par.second left.second r.second;}virtual void OnUpdate(TSave save, const int len, const TRecord iUpdate) override{save.second save.first * 2 * iUpdate C1097Int(len) * iUpdate * iUpdate;save.first C1097Int(iUpdate) * len;}
};单点初始化
【线段树】【众数】1157数组中占绝大多数的元素
templateclass TSave std::pairint,int, class TRecord int
class CMyLineTree : public CSingUpdateLineTreeTSave, TRecord
{
public:CMyLineTree(const vectorint arr):m_moreNum(arr),CSingUpdateLineTreeTSave,TRecord(arr.size()){m_arr arr; CSingUpdateLineTreeTSave, TRecord::Init();}int Query(int left, int r, int threshold){m_vCan.clear();CSingUpdateLineTreeTSave, TRecord::Query(left,r);auto [i1, i2] m_moreNum.Query(left, r, m_vCan);return (i2 threshold) ? i1 : -1;}
protected:vectorint m_vCan;virtual void OnQuery(TSave save) override {m_vCan.emplace_back(save.first);}virtual void OnUpdate(TSave save, const TRecord update) override{};virtual void OnUpdateParent(TSave par, const TSave left, const TSave r, int iSaveLeft, int iSaveRight) override {vectorint vCan { left.first,r.first };par m_moreNum.Query(iSaveLeft - 1, iSaveRight - 1, vCan);} vectorint m_arr;CMoreNum m_moreNum;virtual void OnInit(TSave save, int iSave) override {save { m_arr[iSave - 1],1 };}
};【线段树】2213. 由单个字符重复的最长子字符串
templateclass TSave std::tupleint,int,int, class TRecord char, class TSaveCon CUnorderMapSaveTSave
class CMyLineTree :public CSingUpdateLineTreeTSave,TRecord, TSaveCon
{
public:CMyLineTree(const string s) :m_s(s), CSingUpdateLineTreeTSave, TRecord, TSaveCon(s.length() ,{ 0,0,0 }) {}void Update(int index, TRecord update) {m_s[index] update;CSingUpdateLineTreeTSave, TRecord, TSaveCon::Update(index, update);}
protected:virtual void OnInit(TSave save, int iSave) override{save { 1,1,1 };}virtual void OnQuery(TSave save) override{}virtual void OnUpdate(TSave save, int iSaveLeft, const TRecord update) override{save { 1,1,1 };}virtual void OnUpdateParent(TSave par, const TSave left, const TSave r, int iSaveLeft, int iSaveRight) override{int i1 get0(left);//最长前缀int i2 max(get1(left), get1(r));//最长字符串int i3 get2(r);//最长后缀const int mid iSaveLeft (iSaveRight - iSaveLeft) / 2;if (m_s[mid] m_s[mid 1]){//拼接i2 max(i2, get2(left) get0(r));if (mid - iSaveLeft 1 i1) {i1 get0(r);}if (iSaveRight - mid i3) {i3 get2(left);}}par { i1,i2,i3 };}string m_s;
};【线段树】2276. 统计区间中的整数数目
templateclass TSaveint, class TRecord int
class CMyTreeRangeLineTree : public CTreeRangeLineTreeTSave, TRecord
{
public:using CTreeRangeLineTreeTSave, 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-iSaveLeft1);}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;}
};【线段树 有序映射】715. Range 模块
templateclass TSaveint, class TRecord int
class CMyTreeRangeLineTree : public CTreeRangeLineTreeTSave, TRecord
{
public:using CTreeRangeLineTreeTSave, TRecord::CTreeRangeLineTree;bool queryRange(int left, int right) {m_bHas true;CTreeRangeLineTreeTSave, TRecord::Query(left, right);return m_bHas;}
protected:bool m_bHas true;virtual void OnQuery(const TSave save, const int iSaveLeft, const int iSaveRight) override{m_bHas (save (iSaveRight - iSaveLeft 1));}virtual void OnUpdate(TSave save, const int iSaveLeft, const int iSaveRight, const TRecord update) override{ save update*(iSaveRight-iSaveLeft1);}virtual void OnUpdateParent(TSave par, const TSave left, const TSave r, const int iSaveLeft, const int iSaveRight) override{par left r;}virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) override{old newRecord;}
};其它有题解的题目
【键值皆有序map 线段树 数学 】100240. 最小化曼哈顿距离|最小线段树单点更新区间查询
templateclass TSaveint, class TRecord int
class CMyTreeRangeLineTree : public CTreeRangeLineTreeTSave, TRecord
{
public:using CTreeRangeLineTreeTSave, TRecord::CTreeRangeLineTree;bool queryRange(int left, int right) {m_bHas true;CTreeRangeLineTreeTSave, TRecord::Query(left, right);return m_bHas;}
protected:bool m_bHas true;virtual void OnQuery(TSave save, int iSaveLeft, int iSaveRight) override{m_bHas (save (iSaveRight - iSaveLeft 1));}virtual void OnUpdate(TSave save, int iSaveLeft, int iSaveRight, const TRecord update) override{ save update*(iSaveRight-iSaveLeft1);}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;}
};无题解的题目
LeetCodeLeetCode 218 际线问题最大值 离散化后 线段树区间修改单点查询LeetCode 315. 计算右侧小于当前元素的个数求和单点修改区间查询LeetCode 327. 区间和的个数求和前缀和是已知的所以离散化。单点修改区间查询LeetCode 493. 翻转对求和离散化后单点修改区间查询LeetCode 699. 掉落的方块最大值区间修改区间查询LeetCode 715. Range 模块求和无法离散化麻烦。直接模拟或差分数组树状数组。 区间修改区间查询。LeetCode 732. 我的日程安排表 III最大值,区间更新区间查询LeetCode 850. 矩形面积 II求和离散化扫描线。线段树实现维护当前x各y是否被覆盖。可以覆盖多次也可以解除覆盖。有覆盖时求和时为1没覆盖为0。LeetCode 1505. 最多 K 次交换相邻数位后得到的最小整数求和单点更新单点查询1521. 找到最接近目标值的函数值与和二分查找。除了练习没有任何必要使用线段树。1649. 通过指令创建有序数组求和单点更新区间修改2179. 统计数组中好三元组数目等价转换重新编码)求和单点更新区间求和2213. 由单个字符重复的最长子字符串最长单点修改区间查询2276. 统计区间中的整数数目无法离散化用哈希。区间修改、区间查询2407. 最长递增子序列 II最大值单点修改区间查询2426. 满足不等式的数对数目离散化求和单点修改2569. 更新数组后处理求和查询01反转区间修改2736. 最大和查询离线查询最大值。单点更新区间查找2926. 平衡子序列的最大和最大值单点更新区间查询2940. 找到 Alice 和 Bob 可以相遇的建筑二分查找最大值线段树3072. 将元素分配到两个数组中 II求和单点修改区间查询LCP 05. 发 LeetCoinDFS时间序求和线段树。区间修改、区间查询LCP 09. 最小跳跃次数最小值单点更新区间查询 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
