简单在线统计
------------

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

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

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

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


.. toctree::
   :maxdepth: 2

   sec02/221_mono_intervals
   sec02/222_road_block
   sec02/223_kadanes_algo
   sec02/224_prefix_sum
   sec02/225_diff
   sec02/226_two_points