Y n o i 数 数 题
先化一下单次方差的式子：
[egin{align}
&frac{sum a_i^2 - 2sum a_i cdot ar{a} + sumar{a}^2}{n}&\
=&frac{1}{n}sum a_i^2 - frac{2}{n} sum a_i ar{a} + ar{a}^2&\
=&frac{1}{n}sum a_i^2 - frac{1}{n^2} left(sum a_i
ight)^2&\
end{align}
]
用 (S) 表示一个下标集合，这样答案就可以表示成：
[sum_{Sin {1,2,3,dots,n}} frac{1}{|S|}left(sum_{iin S} a_i^2
ight) - frac{1}{|S|}left(sum_{iin S} a_i
ight) ^ 2
]
先搞前面的式子，考虑枚举集合大小 (k) 和每个元素的贡献，计数的时候可以用钦定法解决，可以得到：
[egin{align}
&sum_k frac{1}{k} {n - 1choose k - 1} sum_{i=1}^n a_i^2&\
=&sum_k frac{1}{k} frac{(n - 1)!}{(k - 1)!(n - k)!} sum_{i=1}^n a_i^2&\
=&frac{1}{n} sum_k {nchoose k} sum_{i=1}^n a_i^2&\
=&frac{2^n - 1}{n} sum_{i=1}^n a_i^2&\
end{align}
]
再搞后面的式子，先把平方写成 (sum_{i=1}^n sum_{j=1}^n a_i a_j) ，对于 (i=j) 和 (i eq j) 的情况分类讨论算贡献。
- (i = j)
[egin{align}
&sum_k frac{1}{k^2} {n - 1 choose k - 1} sum_{i=1}^n a_i^2&\
=&sum_k frac{1}{k^2} frac{(n-1)!}{(k-1)!(n-k)!} sum_{i=1}^n a_i^2&\
=&frac{1}{n} sum_k frac{1}{k} frac{n!}{k!(n - k)!} sum_{i=1}^n a_i^2&\
=&frac{1}{n} f(n) cdot sum_{i=1}^n a_i^2&\
end{align}
]
其中 (f(n) = sum_k frac{1}{k} {n choose k}) .
考虑预处理，考虑差分：
[egin{align}
f(n) - f(n - 1) =& frac{1}{n}cdot {nchoose n} + sum_{i=1}^{n - 1} frac{1}{k} cdot left({n choose k} - {n choose k - 1}
ight)&\
=& frac{1}{n} + sum_{i=1}^{n - 1} frac{1}{k} {n - 1choose k - 1}&\
=& frac{1}{n} + frac{2^n - 2}{n}&\
=& frac{2^n - 1}{n}&\
end{align}
]
- (i eq j)
[egin{align}
&sum_k frac{1}{k^2} {n - 2choose k - 2} left(left(sum_{i=1}^n a_i
ight) ^ 2 - sum_{i=1}^n a_i^2
ight)&\
=&sum_k frac{1}{k^2} frac{(n-2)!}{(k-2)!(n-k)!}left(left(sum_{i=1}^n a_i
ight) ^ 2 - sum_{i=1}^n a_i^2
ight)&\
=&frac{1}{ncdot (n - 1)} sum_k frac{k - 1}{k} frac{n!}{k!(n - k)!}left(left(sum_{i=1}^n a_i
ight) ^ 2 - sum_{i=1}^n a_i^2
ight)&\
=&frac{1}{ncdot (n - 1)} sum_k left({nchoose k} - frac{{nchoose k}}{k}
ight) left(left(sum_{i=1}^n a_i
ight) ^ 2 - sum_{i=1}^n a_i^2
ight)&\
=&frac{2 ^ n - 1 - f(n)}{ncdot (n - 1)}left(left(sum_{i=1}^n a_i
ight) ^ 2 - sum_{i=1}^n a_i^2
ight)&\
end{align}
]
然后用线段树维护一下 (F = sum_{i=l}^r a_i) 和 (G = sum_{i=l}^r a_i^2) .
答案就是：
[frac{2^n - 1}{n} F - frac{Fcdot f(len)}{len} - frac{2^n - 1 - f(len)}{lencdot (len - 1)} (G^2 - F)
]
时间复杂度 (mathcal{O}(mlog n)) .