3.2. 简单在线统计

统计算法用于对一系列数据进行统计指标计算，比如平均数、最大值、最小值、方差、区间和、中值等等。统计算法在数值算法中有广泛应用，一些简单的统计指标例如最大值、最小值、平均值往往是更复杂的数值算法中的基础计算单元，有些复杂的统计指标的计算例如最大区间和、多组数据的中值等本身就是非常有技巧的算法问题，有些统计指标例如单调区间统计、前缀和等可以用来构造其他精巧的算法。

在线算法（online algorithms）是指在读数据的同时完成算法运算，读入的数据不储存下来，数据读完，结果就计算出来的算法。比如最简单的求n个数的平均值，通过一个单循环一边读入数据，一边进行累加，同时记录数据的个数。一旦数据读完，循环结束之后用平均值公式进行一次计算就可以得出结果。在线算法的时间复杂度一定是\(O(n)\)。

在线统计算法顾名思义，就是用于计算统计指标的在线算法。数据只读一遍，并不保存，读完之后指标就计算完成。

虽说本部分讨论简单在线统计算法，但我们并不打算讨论怎样计算平均数、最大值、最小值、方差这几个可以通过一个简单的算术公式计算出的简单指标。我们会对较为复杂一点的单调区间统计、最大区间和、前缀和、差分法、尺读法以及它们的典型应用进行介绍。

• 3.2.1. 单调区间在线统计
  • 3.2.1.1. 最长单调区间问题（洛谷P1567）
  • 3.2.1.2. 最大单调区间振幅
• 3.2.2. 单调区间问题的应用：两个NOIP提高组复赛题
  • 3.2.2.1. 积木大赛（NOIP2013-S组1.1，洛谷P1969）
  • 3.2.2.2. 铺设道路（NOIP2018-S组1.1，洛谷P5019）
• 3.2.3. 最大区间和问题（洛谷P1115）
• 3.2.4. 前缀和
  • 3.2.4.1. 一维前缀和
  • 3.2.4.2. 二维前缀和
  • 3.2.4.3. 前缀和的常见应用
• 3.2.5. 差分法（洛谷P3397）
  • 3.2.5.1. 线性差分
  • 3.2.5.2. 二维差分（洛谷P3397）
• 3.2.6. 尺取法（洛谷P1147）