AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【线段树】1622. 奇妙序列

2024-04-10 40
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【线段树】1622. 奇妙序列

本文涉及知识点

设计 数学 线段树

本文基础解法

【设计】 【数学】1622 奇妙序列

LeetCode1622. 奇妙序列

请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。

请实现 Fancy 类 ：

Fancy() 初始化一个空序列对象。

void append(val) 将整数 val 添加在序列末尾。

void addAll(inc) 将所有序列中的现有数值都增加 inc 。

void multAll(m) 将序列中的所有现有数值都乘以整数 m 。

int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 109 + 7 取余。如果下标大于等于序列的长度，请返回 -1 。

示例：

输入：

[“Fancy”, “append”, “addAll”, “append”, “multAll”, “getIndex”, “addAll”, “append”, “multAll”, “getIndex”, “getIndex”, “getIndex”]

[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]

输出：

[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释：

Fancy fancy = new Fancy();

fancy.append(2); // 奇妙序列：[2]

fancy.addAll(3); // 奇妙序列：[2+3] -> [5]

fancy.append(7); // 奇妙序列：[5, 7]

fancy.multAll(2); // 奇妙序列：[52, 72] -> [10, 14]

fancy.getIndex(0); // 返回 10

fancy.addAll(3); // 奇妙序列：[10+3, 14+3] -> [13, 17]

fancy.append(10); // 奇妙序列：[13, 17, 10]

fancy.multAll(2); // 奇妙序列：[132, 172, 10*2] -> [26, 34, 20]

fancy.getIndex(0); // 返回 26

fancy.getIndex(1); // 返回 34

fancy.getIndex(2); // 返回 20

提示：

1 <= val, inc, m <= 100

0 <= idx <= 105

总共最多会有 105 次对 append，addAll，multAll 和 getIndex 的调用。

线段树

由于最多105个元素，故线段树的元素个数105，初始全部为0。m_iSize记录已经插入的数据。

插入相当于对m_iSize单点更新（加法），乘和加相当于区域[0,m_iSize-1]更新。

std::pair记录更新的参数。first表示要乘的数，second 表示要加的数。两次操作合并的代码如下：

virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
    {
      old.first *= newRecord.first;
      old.second = old.second * newRecord.first + newRecord.second;
    }

推导过程x先乘以a,加b；在乘以c，加d。

x1 = ax +b

x2 = axc + bc + d

相当于：x直接乘以 ab 后加bc+d。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
  C1097Int(long long llData = 0) :m_iData(llData% MOD)
  {
  }
  C1097Int  operator+(const C1097Int& o)const
  {
    return C1097Int(((long long)m_iData + o.m_iData) % MOD);
  }
  C1097Int& operator+=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData + o.m_iData) % MOD;
    return *this;
  }
  C1097Int& operator-=(const C1097Int& o)
  {
    m_iData = (m_iData + MOD - o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator-(const C1097Int& o)
  {
    return C1097Int((m_iData + MOD - o.m_iData) % MOD);
  }
  C1097Int  operator*(const C1097Int& o)const
  {
    return((long long)m_iData * o.m_iData) % MOD;
  }
  C1097Int& operator*=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData * o.m_iData) % MOD;
    return *this;
  }
  bool operator==(const C1097Int& o)const
  {
    return m_iData == o.m_iData;
  }
  bool operator<(const C1097Int& o)const
  {
    return m_iData < o.m_iData;
  }
  C1097Int pow(long long n)const
  {
    C1097Int iRet = 1, iCur = *this;
    while (n)
    {
      if (n & 1)
      {
        iRet *= iCur;
      }
      iCur *= iCur;
      n >>= 1;
    }
    return iRet;
  }
  C1097Int PowNegative1()const
  {
    return pow(MOD - 2);
  }
  int ToInt()const
  {
    return m_iData;
  }
private:
  int m_iData = 0;;
};
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);
  }
  template<class TGet>
  void Query(const TGet& oGet, int iLeftIndex, int iRightIndex)
  {
    Query(oGet, 1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
  }
private:
  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& iUpdate) = 0;
  template<class TGet>
  void Query(const TGet& oGet, int iNode, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight)
  {
    if ((iQueryLeft <= iSaveLeft) && (iQueryRight >= iSaveRight))
    {
      oGet(m_vArr[iNode]);
      return;
    }
    Fresh(iNode, iSaveLeft, iSaveRight);
    const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iMid >= iQueryLeft)
    {
      Query(oGet, iNode * 2, iSaveLeft, iMid, iQueryLeft, iQueryRight);
    }
    if (iMid + 1 <= iQueryRight)
    {
      Query(oGet, 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;
};
  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;
    }
  };
  class Fancy {
  public:
    Fancy() :m_lineTree(100'000, { 1,0 }) {
    }
    void append(int val) {
      m_lineTree.Update(m_iSize, m_iSize, { 1,val });
      m_iSize++;
    }
    void addAll(int inc) {
      m_lineTree.Update(0, m_iSize - 1, { 1,inc });
    }
    void multAll(int m) {
      m_lineTree.Update(0, m_iSize - 1, { m,0 });
    }
    int getIndex(int idx) {
      if (idx >= m_iSize)
      {
        return -1;
      }
      C1097Int<> iiRet = 0;
      auto Get = [&](const C1097Int<>& value ) {
        iiRet += value;
      };
      m_lineTree.Query(Get,idx,idx);
      return iiRet.ToInt();
    }
    CMyLineTree<> m_lineTree;
    int m_iSize=0;
  };

旧代码

旧类库，将TRecord 的默认值 设计成参数，编辑器对次有限制。改成成员变量。

template
class C1097Int
{
public:
C1097Int(long long llData = 0) :m_iData(llData% MOD)
{
}
C1097Int  operator+(const C1097Int& o)const
{
  return C1097Int(((long long)m_iData + o.m_iData) % MOD);
}
C1097Int& operator+=(const C1097Int& o)
{
  m_iData = ((long long)m_iData + o.m_iData) % MOD;
  return *this;
}
C1097Int& operator-=(const C1097Int& o)
{
  m_iData = (m_iData + MOD - o.m_iData) % MOD;
  return *this;
}
C1097Int  operator-(const C1097Int& o)
{
  return C1097Int((m_iData + MOD - o.m_iData) % MOD);
}
C1097Int  operator*(const C1097Int& o)const
{
  return((long long)m_iData * o.m_iData) % MOD;
}
C1097Int& operator*=(const C1097Int& o)
{
  m_iData = ((long long)m_iData * o.m_iData) % MOD;
  return *this;
}
bool operator<(const C1097Int& o)const
{
  return m_iData < o.m_iData;
}
C1097Int pow(long long n)const
{
  C1097Int iRet = 1, iCur = *this;
  while (n)
  {
    if (n & 1)
    {
      iRet *= iCur;
    }
    iCur *= iCur;
    n >>= 1;
  }
  return iRet;
}
C1097Int PowNegative1()const
{
  return pow(MOD - 2);
}
int ToInt()const
{
  return m_iData;
}
private:
int m_iData = 0;;
};
template<class TSave, class TRecord, TRecord RecordNull = 0>
class CLineTree
{
public:
CLineTree(int iEleSize)
:m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4), m_vRecord(m_iEleSize * 4, RecordNull)
{
}
void Update(int iLeftIndex, int iRightIndex, TRecord value)
{
  Update(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1, value);
}
template<class TGet>
void Query(const TGet& oGet, int iLeftIndex, int iRightIndex)
{
  Query(oGet, 1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
}
private:
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& iUpdate) = 0;
template
void Query(const TGet& oGet, int iNode, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight)
{
if ((iQueryLeft <= iSaveLeft) && (iQueryRight >= iSaveRight))
{
oGet(m_vArr[iNode]);
return;
}
Fresh(iNode, iSaveLeft, iSaveRight);
const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iMid >= iQueryLeft)
{
Query(oGet, iNode * 2, iSaveLeft, iMid, iQueryLeft, iQueryRight);
}
if (iMid + 1 <= iQueryRight)
{
Query(oGet, 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 (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] = RecordNull;
}
const int m_iEleSize;
vector m_vArr;
vector m_vRecord;
};
const long long llUnit = 2000’000’000;
template<class TSave = C1097Int<>, class TRecord = long long, TRecord RecordNull = llUnit >
class CMyLineTree : public CLineTree<TSave, TRecord, RecordNull>
{
public:
using CLineTree<TSave, TRecord, RecordNull>::CLineTree;
protected:
virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
{
long long mul = (old/ llUnit) * (newRecord/ llUnit);
long long add = (old% llUnit) * (newRecord/ llUnit) + (newRecord% llUnit);
old = C1097Int<>(mul).ToInt()*llUnit + C1097Int<>(add).ToInt();
}
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/ llUnit) + iUpdate% llUnit ;
}
};
class Fancy {
public:
Fancy():m_lineTree(100’000){
}
void append(int val) {
m_lineTree.Update(m_iSize, m_iSize, llUnit + val );
m_iSize++;
}
void addAll(int inc) {
m_lineTree.Update(0, m_iSize-1, llUnit + inc);
}
void multAll(int m) {
m_lineTree.Update(0, m_iSize - 1, llUnit *m);
}
int getIndex(int idx) {
if (idx >= m_iSize)
{
return -1;
}
C1097Int<> iiRet = 0;
auto Get = [&](const C1097Int<>& value ) {
iiRet += value;
};
m_lineTree.Query(Get,idx,idx);
return iiRet.ToInt();
}
CMyLineTree<> m_lineTree;
int m_iSize=0;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

文章标签：
算法
C++
C#
测试技术
API
闻缺陷则喜何志丹
目录
相关文章
qiuqiushuibx
|
算法
代码随想录 Day26 贪心算法01 中 LeetCode T376 摆动序列
代码随想录 Day26 贪心算法01 中 LeetCode T376 摆动序列
qiuqiushuibx
59 1
狗哥不是甜妹
|
6月前
|
存储 算法
算法训练，牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练，牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
狗哥不是甜妹
47 0
算法训练，牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
炫酷的伊莉娜
|
7月前
【错题集-编程题】最长上升子序列（二）（贪心 + 二分）
【错题集-编程题】最长上升子序列（二）（贪心 + 二分）
炫酷的伊莉娜
41 0
Hsu琛君珩
|
算法
代码随想录算法训练营第三十一天 | LeetCode 455. 分发饼干、376. 摆动序列、53. 最大子数组和
代码随想录算法训练营第三十一天 | LeetCode 455. 分发饼干、376. 摆动序列、53. 最大子数组和
Hsu琛君珩
68 0
东离与糖宝
|
机器学习/深度学习 算法 JavaScript
代码随想录训练营day31| 455.分发饼干 376. 摆动序列 53. 最大子序和
代码随想录训练营day31| 455.分发饼干 376. 摆动序列 53. 最大子序和
东离与糖宝
57 0
不懂开发的程序猿
|
算法
LeetCode算法小抄--花式遍历二叉树
LeetCode算法小抄--花式遍历二叉树
不懂开发的程序猿
201 0
m5suanqf6o2n6
|
算法
经典算法题---链表奇偶重排(好题)&&双指针系列
经典算法题---链表奇偶重排(好题)&&双指针系列
m5suanqf6o2n6
111 0
经典算法题---链表奇偶重排(好题)&&双指针系列
游客d7sf7jc5pjjba
|
算法
leetcode每日一题：376. 摆动序列
leetcode每日一题：376. 摆动序列
游客d7sf7jc5pjjba
64 0
安度因123
|
算法
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
安度因123
146 0
【每日挠头算法题】Acwing 756. 蛇形矩阵 —— 巧妙解法
游客mpyaunfezolqe
|
算法
代码随想录刷题|贪心算法理论 LeetCode455.分发饼干 376. 摆动序列 53. 最大子序和
代码随想录刷题|贪心算法理论 LeetCode455.分发饼干 376. 摆动序列 53. 最大子序和
游客mpyaunfezolqe
89 0
代码随想录刷题|贪心算法理论 LeetCode455.分发饼干 376. 摆动序列 53. 最大子序和

热门文章

最新文章

  • 1
    天猫精灵开放平台-之小百科测评
  • 2
    语义检索系统：基于Milvus 搭建召回系统抽取向量进行检索，加速索引
  • 3
    3D立方体图片切换动画
  • 4
    模态对话框和非模态对话框
  • 5
    java03
  • 6
    冒泡排序
  • 7
    Windows XP客户端加域操作手册上
  • 8
    微信 6.5.1 for iOS发布 可以在朋友圈分享相册中的视频
  • 9
    Chapter 1: Creating the GUI Form and Adding Widgets
  • 10
    【Mockplus教程】帐号和购买
  • 1
    「Mac畅玩鸿蒙与硬件42」UI互动应用篇19 - 数字键盘应用
    33
  • 2
    赋能加速AI应用交付，F5 BIG-IP Next for Kubernetes方案解读
    28
  • 3
    RAG分块策略：主流方法（递归、jina-seg）+前沿推荐（Meta-chunking、Late chunking、SLM-SFT）
    24
  • 4
    Python学习的自我理解和想法（2）
    25
  • 5
    Transformer图解
    31
  • 6
    API安全专题：如何有效应对新型Bot攻击？
    17
  • 7
    Selenium IDE：Web自动化测试的得力助手
    31
  • 8
    《docker高级篇（大厂进阶）：5.Docker-compose容器编排》包括是什么能干嘛去哪下、Compose核心概念、Compose使用三个步骤、Compose常用命令、Compose编排微服务
    47
  • 9
    24/7全时守护：AI视频监控技术的深度实现与应用分享
    38
  • 10
    《docker高级篇（大厂进阶）：6.Docker轻量级可视化工具Portainer》
    25

    • 相关电子书

    更多
  • 图解算法小抄
  • 低代码开发师（初级）实战教程
  • 阿里巴巴DevOps 最佳实践手册

    • 相关实验场景

    更多
  • 欧拉图的构造性证明与算法实现
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月