提供另一个公式
  • 板块P1471 方差
  • 楼主王则昱wzy
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/30 14:40
  • 上次更新2024/6/30 17:51:19
查看原帖
提供另一个公式
388807
王则昱wzy楼主2024/6/30 14:40

看题解中没人用，想介绍一下

有一个有x项的数列X，一个有y项的数列Y\text{有一个有} x \text{项的数列}X\text{，一个有} y\text{项的数列} Y X和Y合并为一个有n项的数列ZX\text{和}Y\text{合并为一个有}n\text{项的数列}Z n=x+yn=x+y Zˉ=xnXˉ+ynYˉ\bar{Z}=\frac{x}{n}\bar{X}+\frac{y}{n}\bar{Y} sZ2=1n(∑i=1x(Xi−Zˉ)2+∑i=1y(Yi−Zˉ)2)=1n(∑i=1x(Xi−Xˉ+Xˉ−Zˉ)2+∑i=1y(Yi−Yˉ+Yˉ−Zˉ)2)=1n(∑i=1x((Xi−Xˉ)2+2×(Xi−Xˉ)×(Xˉ−Zˉ)+(Xˉ−Zˉ)2)+∑i=1y((Yi−Yˉ)2+2×(Yi−Yˉ)×(Yˉ−Zˉ)+(Yˉ−Zˉ)2))=1n(∑i=1x(Xi−Xˉ)2+2∑i=1x(Xi−Xˉ)(Xˉ−Zˉ)+x(Xˉ−Zˉ)2+∑i=1y(Yi−Yˉ)2+2∑i=1y(Yi−Yˉ)(Yˉ−Zˉ)+y(Yˉ−Zˉ)2)\begin{aligned} s^{2}_Z&=\frac{1}{n}(\sum_{i=1}^{x}(X_{i}-\bar{Z})^{2}+\sum_{i=1}^{y}(Y_{i}-\bar{Z})^{2})\\ &=\frac{1}{n}(\sum_{i=1}^{x}(X_{i}-\bar{X}+\bar{X}-\bar{Z})^{2}+\sum_{i=1}^{y}(Y_{i}-\bar{Y}+\bar{Y}-\bar{Z})^{2})\\ &=\frac{1}{n}(\sum_{i=1}^{x}((X_{i}-\bar{X})^2+2\times(X_i-\bar{X})\times(\bar{X}-\bar{Z})+(\bar{X}-\bar{Z})^{2})+\sum_{i=1}^{y}((Y_{i}-\bar{Y})^2+2\times(Y_i-\bar{Y})\times(\bar{Y}-\bar{Z})+(\bar{Y}-\bar{Z})^{2}))\\ &=\frac{1}{n}(\sum_{i=1}^{x}(X_{i}-\bar{X})^2+2\sum_{i=1}^x(X_i-\bar{X})(\bar{X}-\bar{Z})+x(\bar{X}-\bar{Z})^{2}+\sum_{i=1}^{y}(Y_{i}-\bar{Y})^2+2\sum_{i=1}^y(Y_i-\bar{Y})(\bar{Y}-\bar{Z})+y(\bar{Y}-\bar{Z})^{2}) \end{aligned} 由于∑i=1x(Xi−Xˉ)=0∑i=1y(Yi−Yˉ)=0sX2=1x∑i=1x(Xi−Xˉ)2sY2=1y∑i=1y(Yi−Yˉ)2将上式化简得sZ2=xn(sX2+(Xˉ−Zˉ)2)+yn(sY2+(Yˉ−Zˉ)2)\begin{aligned} \text{由于}&\sum_{i=1}^x(X_i-\bar{X})=0\\ &\sum_{i=1}^y(Y_i-\bar{Y})=0\\ &s^2_X=\frac{1}{x}\sum_{i=1}^{x}(X_{i}-\bar{X})^2\\ &s^2_Y=\frac{1}{y}\sum_{i=1}^{y}(Y_{i}-\bar{Y})^2\\ \text{将上式化简得} &s^{2}_Z=\frac{x}{n}(s^2_X+(\bar{X}-\bar{Z})^2)+\frac{y}{n}(s^2_Y+(\bar{Y}-\bar{Z})^2) \end{aligned}

通过这个公式，我们可以在线段树中直接存储均值和方差。并且在做区间加操作时对信息的修改非常简单（均值+k+k,方差不变）

2024/6/30 14:40