統計において、データの散らばり度合いを表す数である分散について説明しよう。

数列a[1], a[2], …, a[n]があるとき、

• a[1]からa[n]までの合計をnで割ったものが平均mである。
• それぞれのa[k]について、mとの差の二乗を計算し、その合計値をnで割ったものが分散(σ^2)である。

数列上のある区間の分散を計算したい。

ここに数列 A[0], A[1], ... A[N-1]がある。最初に init(N, A) によって A の初期値が与えられる。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ init(N, A):
  • N -- 数列の長さ。数列の各項には 0 から N-1 までの異なる整数の番号がつけられている。
  • A -- 数列の各項を表す整数の配列。0 ≦ i ＜ N に対し 1 ≦ A[i] ≦ 10 000 を仮定してよい。
  このプロシージャは最初に update(i, x) または variance(i, j) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ update(i, x):
  • i -- 値が変化する数列の項の番号。0 ≦ i ＜ N を仮定してよい。
  • x -- 値が変化した後の i 番目の項の値。0 ≦ x ≦ 10 000 を仮定してよい。
  このプロシージャは複数回呼び出される。1回の呼び出しは1回の数列の値の変化に対応する。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ variance(i, j):
  • i -- 分散を計算したい区間のはじめの項の番号。 0 ≦ i ＜ N を仮定してよい。
  • j -- 分散を計算したい区間の最後の項の番号。 i ≦ j ＜ N を仮定してよい。
  このプロシージャは複数回呼び出される。それぞれの呼び出しに大して i 番目の項から j 番目の項(両端も含む)までの(j - i + 1)個の値を母集団としたときの分散を戻り値として返す必要がある。小数点以下の値は切り捨てて整数値にして返すこと。

N = 3, A[i] の初期値が

の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後、複数回の update または variance の呼び出しが任意の順番で行われる。以下に呼び出しと正しい戻り値の例を示す: