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

【线段树】1622. 奇妙序列

2024-04-10 73
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【线段树】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
闻缺陷则喜何志丹
目录
相关文章
阿珊和她的猫
|
存储 自然语言处理 JavaScript
深入理解JS的执行上下文、词法作用域和闭包(上)
深入理解JS的执行上下文、词法作用域和闭包(上)
阿珊和她的猫
306 0
liuyunshengsir
|
Java 数据库连接 数据库
springboot 集成kingbase的步骤
要在Spring Boot中集成Kingbase数据库，你可以按照以下步骤进行操作： 步骤1：添加Kingbase JDBC驱动 首先，将Kingbase JDBC驱动程序添加到Spring Boot项目的依赖项中。你可以在Maven或Gradle构建文件中添加以下依赖项（根据你使用的构建管理工具进行选择）： 对于Maven： ```xml <dependency> <groupId>com.kingbase</groupId> <artifactId>kingbase-driver</artifactId> <version>{驱动版本}</version> </
liuyunshengsir
1837 0
Star时光
|
12月前
|
存储 关系型数据库 MySQL
MySQL在企业内部应用场景有哪些
【10月更文挑战第17天】MySQL在企业内部应用场景有哪些
Star时光
430 0
SelectDB
|
9月前
|
存储 SQL 监控
计算效率提升 10 倍，存储成本降低 60%，灵犀科技基于 Apache Doris 建设统一数据服务平台
灵犀科技早期基于 Hadoop 构建大数据平台，在战略调整和需求的持续扩增下，数据处理效率、查询性能、资源成本问题随之出现。为此，引入 [Apache Doris](https://doris.apache.org/) 替换了复杂技术栈，升级为集存储、加工、服务为一体的统一架构，实现存储成本下降 60%，计算效率提升超 10 倍的显著成效。
SelectDB
363 0
计算效率提升 10 倍，存储成本降低 60%，灵犀科技基于 Apache Doris 建设统一数据服务平台
敏叔V587
|
存储 SQL 分布式计算
SparkSQL优化策略大盘点
SparkSQL优化策略大盘点
敏叔V587
195 0
shuj
|
11月前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习中的卷积神经网络（CNN）： 从理论到实践
本文将深入浅出地介绍卷积神经网络（CNN）的工作原理，并带领读者通过一个简单的图像分类项目，实现从理论到代码的转变。我们将探索CNN如何识别和处理图像数据，并通过实例展示如何训练一个有效的CNN模型。无论你是深度学习领域的新手还是希望扩展你的技术栈，这篇文章都将为你提供宝贵的知识和技能。
shuj
937 7
小王老师呀
|
iOS开发 MacOS 内存技术
如何创建可引导的 macOS Sonoma 安装介质
【8月更文挑战第23天】以下是创建可引导的macOS Sonoma安装介质的步骤： 1. 运行macOS的电脑，确保有足够的存储空间和稳定的网络连接。 2. 至少16GB的USB闪存驱动器或外部硬盘，格式化为Mac OS扩展（日志式），并命名为“Installer”。
小王老师呀
298 3
以山向海
|
SQL Oracle 关系型数据库
关系型数据库Oracle并行度（Degree of Parallelism, DOP）
【7月更文挑战第12天】
以山向海
518 16
土木林森
|
前端开发 JavaScript Serverless
揭秘CSS布局神器：vw/vh、rem、%与px大PK，掌握它们，让你的网页设计秒变高大上，面试难题迎刃而解！
【8月更文挑战第4天】在Web开发中，合理选择CSS单位对响应式布局至关重要。本文探索viewport单位（vw/vh）、rem、百分比（%）及像素（px）的基础知识与应用场景。通过代码示例，展示如何运用这些单位实现全屏布局、尺寸比例调整、灵活的元素大小及固定尺寸。最后，模拟面试题，介绍如何仅用CSS实现一个元素的高度为其宽度两倍且响应视口变化的方法。
土木林森
662 8
NineData
|
SQL 安全 Cloud Native
NineData数据复制技术助力实时数仓构建，开发人员必读！
NineData 和 SelectDB 共同举办的主题为“实时数据驱动，引领企业智能化数据管理”的线上联合发布会，圆满成功举办！双方聚焦于实时数据仓库技术和数据开发能力，展示如何通过强大的生态开发兼容性，对接丰富的大数据生态产品，助力企业快速开展数据分析业务，共同探索实时数据驱动的未来企业智能化数据管理解决方案。本文根据玖章算术技术副总裁陈长城（天羽）在 NineData X SelectDB 联合发布会的主题演讲内容整理。
NineData
656 0
NineData数据复制技术助力实时数仓构建，开发人员必读！

热门文章

最新文章

  • 1
    如何配置 Java 环境变量：设置 JAVA_HOME 和 PATH
  • 2
    什么是Widevine？Widevine DRM详解
  • 3
    Linux下如何查看高CPU占用率线程 LINUX CPU利用率计算
  • 4
    什么是tomcat？tomcat是干什么用的？
  • 5
    Webpack和Vite的区别
  • 6
    微信小程序：本地开发环境和线上环境配置
  • 7
    数据人必读！玩转数据可视化用这个就够了——高德LOCA API 2.0升级来袭！
  • 8
    Point Grey articles link
  • 9
    数据库负载急剧提高的应急处理(二)
  • 10
    软刀子割肉：智能电视的软陷阱
  • 1
    《政企API网关：安全与性能平衡的转型实践》
    37
  • 2
    《SaaS网关多租户治理：从串流到稳控的实践》
    30
  • 3
    从DQN到Double DQN：分离动作选择与价值评估，解决强化学习中的Q值过估计问题
    32
  • 4
    Aquarius 官方发布 3 级海面密度标准映射图像季节性数据 V5.0
    73
  • 5
    【Azure App Service】Root CA on App Service
    46
  • 6
    基于springboot的非遗传承宣传平台
    47
  • 7
    Proxmox Mail Gateway 9.0 正式版发布 - 全面的开源邮件安全平台
    35
  • 8
    VMware NSX 9.0.1.0 发布 - 下一代网络安全虚拟化平台
    64
  • 9
    爬坑 10 年！京东店铺全量商品接口实战开发：从分页优化、SKU 关联到数据完整性闭环
    39
  • 10
    VMware vSphere 9.0.1.0 发布 - 企业级工作负载平台
    35

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云免费云服务器:个人用户每月750小时免费