K-variance (Editorial)

Let’s consider the sum:

i = 1 \sum n (a_{i} - a ˉ)^{2} = i = 1 \sum n (a_{i} - \frac{\sum _{i = 1}^{n} a _{i}}{n})^{2} = i = 1 \sum n (a_{i}^{2} - \frac{2}{n} a_{i} i = 1 \sum n a_{i} + \frac{( \sum _{i = 1}^{n} a _{i} ) ^{2}}{n ^{2}}) = i = 1 \sum n a_{i}^{2} - \frac{2}{n} i = 1 \sum n a_{i} i = 1 \sum n a_{i} + \frac{( \sum _{i = 1}^{n} a _{i} ) ^{2}}{n} = i = 1 \sum n a_{i}^{2} - \frac{2}{n} (i = 1 \sum n a_{i})^{2} + \frac{1}{n} (i = 1 \sum n a_{i})^{2} = i = 1 \sum n a_{i}^{2} - \frac{1}{n} (i = 1 \sum n a_{i})^{2}

\sum_{i=1}^n (a_i - \bar{a})^2 = \sum_{i=1}^n \left(a_i - \frac{\sum_{i=1}^n a_i}{n} \right)^2 = \sum_{i=1}^n \left(a^2_i - \frac{2}{n} a_i \sum_{i=1}^n a_i + \frac{\left(\sum_{i=1}^n a_i \right)^2}{n^2} \right) = \\ \sum_{i=1}^n a^2_i - \frac{2}{n} \sum_{i=1}^n a_i \sum_{i=1}^n a_i + \frac{\left(\sum_{i=1}^n a_i \right)^2}{n} = \\ \sum_{i=1}^n a^2_i - \frac{2}{n} \left(\sum_{i=1}^n a_i \right)^2 + \frac{1}{n} \left(\sum_{i=1}^n a_i \right)^2 = \sum_{i=1}^n a^2_i - \frac{1}{n} \left(\sum_{i=1}^n a_i \right)^2

Now, the formula for variance can be rewritten as:

\frac{\sum _{i = 1}^{n} ( a _{i} - a ˉ ) ^{2}}{n - 1} = \frac{\sum _{i = 1}^{n} a _{i}^{2} - \frac{1}{n} ( \sum _{i = 1}^{n} a _{i} ) ^{2}}{n - 1}

\sqrt{\sum_{i=1}^n (a_i - \bar{a})^2 \over n - 1} = \sqrt{\frac{\sum_{i=1}^n a^2_i - \frac{1}{n} \left(\sum_{i=1}^n a_i \right)^2}{n - 1}}

If we maintain the sum of the elements of the sequence ${a_{i}, a_{i + 1}, ..., a_{i + k - 1}}$ \{a_i, a_{i+1}, ..., a_{i+k-1}\} (i.e. $(a_{i} + a_{i + 1} + ... + a_{i + k - 1})$ (a_i + a_{i+1} + ... + a_{i+k-1})) and the sum of their squares $(a_{i}^{2} + a_{i + 1}^{2} + ... + a_{i + k - 1}^{2})$ (a^2_i + a^2_{i+1} + ... + a^2_{i+k-1}), then it is possible to calculate the desired variance for the segment in constant time.

Example

Let's expand the numerator of the fraction in the variance $n = 3$ n = 3:

(a_{1} - \frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (a_{2} - \frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (a_{3} - \frac{a _{1} + a _{2} + a _{3}}{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - 2 a_{1} \cdot \frac{a _{1} + a _{2} + a _{3}}{3} - 2 a_{2} \cdot \frac{a _{1} + a _{2} + a _{3}}{3} - 2 a_{3} \cdot \frac{a _{1} + a _{2} + a _{3}}{3} + (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - \frac{2}{3} (a_{1} + a_{2} + a_{3}) (a_{1} + a_{2} + a_{3}) + 3 \cdot (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - \frac{2}{3} (a_{1} + a_{2} + a_{3})^{2} + \frac{1}{3} (a_{1} + a_{2} + a_{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - \frac{1}{3} (a_{1} + a_{2} + a_{3})^{2}

\left(a_1 - \frac{a_1 + a_2 + a_3}{3}\right)^2 + \left(a_2 - \frac{a_1 + a_2 + a_3}{3}\right)^2 + \left(a_3 - \frac{a_1 + a_2 + a_3}{3}\right)^2 = \\ a_1^2 + a_2^2 + a_3^2 - 2a_1 \cdot \frac{a_1 + a_2 + a_3}{3} - 2a_2 \cdot \frac{a_1 + a_2 + a_3}{3} - 2a_3 \cdot \frac{a_1 + a_2 + a_3}{3} + \\ \left(\frac{a_1 + a_2 + a_3}{3}\right)^2 + \left(\frac{a_1 + a_2 + a_3}{3}\right)^2 + \left(\frac{a_1 + a_2 + a_3}{3}\right)^2 = \\ a_1^2 + a_2^2 + a_3^2 - \frac{2}{3}(a_1 + a_2 + a_3)(a_1 + a_2 + a_3) + 3 \cdot \left(\frac{a_1 + a_2 + a_3}{3}\right)^2 = \\ a_1^2 + a_2^2 + a_3^2 - \frac{2}{3}(a_1 + a_2 + a_3)^2 + \frac{1}{3}(a_1 + a_2 + a_3)^2 = \\ a_1^2 + a_2^2 + a_3^2 - \frac{1}{3}(a_1 + a_2 + a_3)^2

Algorithm implementation

Read the input data.

scanf("%d %d", &n, &k);
a.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

On the segment $[i - k + 1; i]$ [i - k + 1; i] let's maintain two variables:

The sum $s u m = a_{i - k + 1} + ... + a_{i - 1} + a_{i}$ sum = a_{i-k+1} + ... + a_{i-1} + a_i,
The sum of squares $s u m 2 = a_{i - k + 1}^{2} + ... + a_{i - 1}^{2} + a_{i}^{2}$ sum2 = a^2_{i-k+1} + ... + a^2_{i-1} + a^2_i

sum = sum2 = 0;

Iterate through the elements of the sequence.

for (i = 0; i < n; i++)
{

Update the values of $s u m$ and $s u m 2$ .

  sum += a[i];
  sum2 += a[i] * a[i];

If there is a window $[i - k + 1; i]$ [i - k + 1; i] of length $k$ , print the result for it.

  if (i >= k - 1)
  {
    printf("%lf\n", sqrt((sum2 - (sum * sum) / k) / (k - 1)));

Remove the element with index $i - k + 1$ i - k + 1 from the considered sequence.

    sum -= a[i - k + 1];
    sum2 -= a[i - k + 1] * a[i - k + 1];
  }
}

i = 1 \sum n (a_{i} - a ˉ)^{2} = i = 1 \sum n (a_{i} - \frac{\sum _{i = 1}^{n} a _{i}}{n})^{2} = i = 1 \sum n (a_{i}^{2} - \frac{2}{n} a_{i} i = 1 \sum n a_{i} + \frac{( \sum _{i = 1}^{n} a _{i} ) ^{2}}{n ^{2}}) = i = 1 \sum n a_{i}^{2} - \frac{2}{n} i = 1 \sum n a_{i} i = 1 \sum n a_{i} + \frac{( \sum _{i = 1}^{n} a _{i} ) ^{2}}{n} = i = 1 \sum n a_{i}^{2} - \frac{2}{n} (i = 1 \sum n a_{i})^{2} + \frac{1}{n} (i = 1 \sum n a_{i})^{2} = i = 1 \sum n a_{i}^{2} - \frac{1}{n} (i = 1 \sum n a_{i})^{2}

(a_{1} - \frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (a_{2} - \frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (a_{3} - \frac{a _{1} + a _{2} + a _{3}}{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - 2 a_{1} \cdot \frac{a _{1} + a _{2} + a _{3}}{3} - 2 a_{2} \cdot \frac{a _{1} + a _{2} + a _{3}}{3} - 2 a_{3} \cdot \frac{a _{1} + a _{2} + a _{3}}{3} + (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} + (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - \frac{2}{3} (a_{1} + a_{2} + a_{3}) (a_{1} + a_{2} + a_{3}) + 3 \cdot (\frac{a _{1} + a _{2} + a _{3}}{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - \frac{2}{3} (a_{1} + a_{2} + a_{3})^{2} + \frac{1}{3} (a_{1} + a_{2} + a_{3})^{2} = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} - \frac{1}{3} (a_{1} + a_{2} + a_{3})^{2}