线段树汇总-阿里云开发者社区

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

区间更新（查询）的时间复杂度是O(logn)，使用懒惰法只会影响以下四类节点，每类节点数量都不超过logn。一，左边界及其祖先。二，右边界及其祖先。三，第一类的兄弟节点。四，第二类的兄弟节点。

本封装类，都是使用数组模拟，如果不是连续的节点，需要离散化。如果是流，无法离散化。则需要用哈希映射或树。

封装类

单点初始化、更新

template<class 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 * 2+1, mid+1, 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( mid+1 <= iQueryRight ){
      Query(iNodeNO * 2+1, mid+1, 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 * 2+1, mid+1, iSaveRight, iUpdateNO, update);
    }
    OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2+1],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;
  vector<TSave> m_vSave;
};

区间更新、区间查询

template<class TSave, class TRecord>
class CLineTree
{
public:
  CLineTree(int iEleSize, TRecord recordNull=0)
    :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;
  vector<TSave> m_vArr;
  vector<TRecord> m_vRecord;
  const TRecord m_recordNull;
};

样例汇总

【线段树】【前缀和】：1687从仓库到码头运输箱子

template<class TSave = int , class TRecord = int>
class CMinLineTree : public CLineTree<TSave, TRecord>
{
public:
  using CLineTree<TSave, 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. 奇妙序列

template<class TSave = C1097Int<>, class TRecord = pair<C1097Int<>,C1097Int<>> >
  class CMyLineTree : public CLineTree<TSave, TRecord>
  {
  public:
    using CLineTree<TSave, 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. 以组为单位订音乐会的门票

template<class TSave, class TRecord, TRecord RecordNull = 0>
class CMaxLineTree : public CLineTree<TSave, 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 CLineTree<pair<C1097Int<>, C1097Int<>>,int>
{
public:
  typedef  pair<C1097Int<>, 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数组中占绝大多数的元素

template<class TSave = std::pair<int,int>, class TRecord = int >
class CMyLineTree : public CSingUpdateLineTree<TSave, TRecord>
{
public:
  CMyLineTree(const vector<int>& arr):m_moreNum(arr),CSingUpdateLineTree<TSave,TRecord>(arr.size()){
    m_arr = arr;    
    CSingUpdateLineTree<TSave, TRecord>::Init();
  }
  int Query(int left, int r, int threshold)
  {
    m_vCan.clear();
    CSingUpdateLineTree<TSave, TRecord>::Query(left,r);
    auto [i1, i2] = m_moreNum.Query(left, r, m_vCan);
    return (i2 >= threshold) ? i1 : -1;
  }
protected:
  vector<int> 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  {
    vector<int> vCan = { left.first,r.first };
    par = m_moreNum.Query(iSaveLeft - 1, iSaveRight - 1, vCan);
  } 
  vector<int> m_arr;
  CMoreNum m_moreNum;
  virtual void OnInit(TSave& save, int iSave) override  {
    save = { m_arr[iSave - 1],1 };
  }
};

【线段树】2213. 由单个字符重复的最长子字符串

template<class TSave = std::tuple<int,int,int>, class TRecord = char, class TSaveCon = CUnorderMapSave<TSave> >
class CMyLineTree :public CSingUpdateLineTree<TSave,TRecord, TSaveCon>
{
public:
  CMyLineTree(const string& s) :m_s(s), CSingUpdateLineTree<TSave, TRecord, TSaveCon>(s.length() ,{ 0,0,0 }) {
  }
  void Update(int index, TRecord update) {
    m_s[index] = update;
    CSingUpdateLineTree<TSave, 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 = get<0>(left);//最长前缀
    int i2 = max(get<1>(left), get<1>(r));//最长字符串
    int i3 = get<2>(r);//最长后缀
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (m_s[mid] == m_s[mid + 1])
    {//拼接
      i2 = max(i2, get<2>(left) + get<0>(r));
      if (mid - iSaveLeft + 1 == i1) {
        i1 += get<0>(r);
      }
      if (iSaveRight - mid == i3) {
        i3 += get<2>(left);
      }
    }
    par = { i1,i2,i3 };
  }
   string m_s;
};

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

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;
  }
};

【线段树有序映射】715. Range 模块

template<class TSave=int, class TRecord =int >
class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord>
{ 
public:
  using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree;
  bool queryRange(int left, int right) {
    m_bHas = true;
    CTreeRangeLineTree<TSave, 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-iSaveLeft+1);
  }
  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. 最小化曼哈顿距离|最小线段树，单点更新，区间查询

template<class TSave=int, class TRecord =int >
class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord>
{ 
public:
  using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree;
  bool queryRange(int left, int right) {
    m_bHas = true;
    CTreeRangeLineTree<TSave, 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-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;
  }
};

【线段树区间位运算模板】3117划分数组得到最小的值之和

template<class TSave = int , class TRecord = int >
class CMyLineTree : public CVectorRangeUpdateLineTree<TSave, TRecord>
{
public:
  CMyLineTree(int iSize,int iNotMay) :CVectorRangeUpdateLineTree<TSave, TRecord>(iSize,iNotMay,iNotMay){
  }
  void Query(int leftIndex, int leftRight) {
    m_iQuery = CVectorRangeUpdateLineTree<TSave, TRecord>::m_recordNull;
    CVectorRangeUpdateLineTree<TSave, TRecord>::Query(leftIndex, leftRight);
  }
  int m_iQuery;
protected:
  virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight)  {
    m_iQuery = min(m_iQuery, save);
  }
  virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) {
    save = min(save,update);
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) {
    par = min(left, r);
  }
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) {
    old = min(newRecord,old);
  }
};

无题解的题目

LeetCode
LeetCode 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. 发 LeetCoin	DFS时间序，求和线段树。区间修改、区间查询
LCP 09. 最小跳跃次数	最小值，单点更新，区间查询

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

线段树汇总

封装类

单点初始化、更新

区间更新、区间查询

样例汇总

单点初始化

其它有题解的题目

无题解的题目

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

线段树汇总

封装类

单点初始化、更新

区间更新、区间查询

样例汇总

单点初始化

其它有题解的题目

无题解的题目

热门文章

最新文章

相关电子书