数据处理 —— 差分

简介: 差分及其实现方法

差分


  考虑一个问题,给出 n 个数据,每次给出一个请求(x, y, k),每次将 x 到 y 位置的数据加上 k,要求在 O(n) 的时间内解决。


  • 暴力解法 —— O(n2),明显不行。
  • 线段树或树状数组 —— O(qlogn),q 为请求次数。
  • 差分 —— O(n),不辱使命。


实现方法


  • 开一个于原数组相同大小的数组用于差分。
  • 进行差分操作,比如需要 2~5 位置的元素都加 1,那么我们就将位置 2 标记为 +1,位置 6 标记为 -1,这样操作所有请求(不懂也先照做)。
  • 计算前缀和,然后再来看结果,就是 q 请求后的结果。
  • 再遍历一次加到原数组即可。


相关文章
|
8月前
|
机器学习/深度学习 数据可视化 算法
数据处理方法—— 7 种数据降维操作 !!
数据处理方法—— 7 种数据降维操作 !!
240 0
|
算法 数据挖掘 计算机视觉
第6章 数据分析——6.2 数据插值
第6章 数据分析——6.2 数据插值
【时间序列分析】——时序分解定理详解
【时间序列分析】——时序分解定理详解
|
7月前
|
数据采集 传感器 移动开发
Karl_AlbrightC# pythonnet(1)_传感器数据清洗算法
/// 读取CSV数据 /// </summary> /// <param name="filePath">文件路径</param> /// <returns>文件中数据集合,都是double类型</returns> static List<double[]> ReadCsvWithCsvHelper(string filePath) { using (var reader = new StreamReader(filePath)) using (var csv = new CsvReader(reader, Cultur
54 13
|
8月前
|
数据可视化 语音技术
时间序列分析实战(三):时序因素分解法
时间序列分析实战(三):时序因素分解法
|
8月前
|
算法
R语言从经济时间序列中用HP滤波器,小波滤波和经验模态分解等提取周期性成分分析
R语言从经济时间序列中用HP滤波器,小波滤波和经验模态分解等提取周期性成分分析
|
数据可视化 数据安全/隐私保护
时序分解 | MATLAB实现基于SWD群体分解的信号分解分量可视化
时序分解 | MATLAB实现基于SWD群体分解的信号分解分量可视化
|
算法 数据处理
数据拟合、参数估计、插值等数据处理算法
数据拟合、参数估计、插值等数据处理算法
164 0
数据拟合、参数估计、插值等数据处理算法
|
机器学习/深度学习 算法 数据可视化
数据归一化:优化数据处理的必备技巧
数据归一化:优化数据处理的必备技巧
|
数据挖掘
专题五数据分析与多项式计算-1
专题五数据分析与多项式计算
58 0