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

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

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为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++**实现。

线段树汇总

封装类

单点初始化、更新

区间更新、区间查询

样例汇总

单点初始化

其它有题解的题目

无题解的题目

热门文章

最新文章

相关电子书