方差

GitHub跳转原题关系图返回列表

线段树同时维护区间和与平方和，用懒标记支持区间加和方差查询。

OJ: luogu

题目 ID: P1471

难度:普及+/提高

标签:线段树懒标记方差浮点数python

日期: 2026-07-16 23:59

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

支持区间每项加上实数，查询区间平均数或方差，结果保留四位小数。

思路

方差可写成 平均(x^2) - 平均(x)^2，所以节点维护 sum = Σx 和 squared = Σx²。区间加 d 时：

sum' = sum + length*d，squared' = squared + 2*d*sum + length*d²。

代码先更新 sum，再用新旧关系计算平方和，并把 d 累加到懒标记。

Python 知识

  • 输入数值用 float，输出使用格式化表达式 f"{value:.4f}"。
  • array("d") 紧凑保存双精度节点字段，避免大量浮点对象。
  • 先保存区间长度 count，平均数和方差公式更直观。

代码

python
import sys
from array import array


sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
values = array("d", map(float, input().split()))
summation = array("d", [0.0]) * (4 * n)
squared = array("d", [0.0]) * (4 * n)
lazy = array("d", [0.0]) * (4 * n)


def apply(node, length, value):
    summation[node] += length * value
    squared[node] += 2 * value * summation[node] - length * value * value
    lazy[node] += value


def build(node, left, right):
    if left == right:
        summation[node] = values[left - 1]
        squared[node] = values[left - 1] ** 2
        return
    middle = (left + right) // 2
    build(node * 2, left, middle)
    build(node * 2 + 1, middle + 1, right)
    summation[node] = summation[node * 2] + summation[node * 2 + 1]
    squared[node] = squared[node * 2] + squared[node * 2 + 1]


def push(node, left, right):
    if lazy[node] == 0 or left == right:
        return
    middle = (left + right) // 2
    apply(node * 2, middle - left + 1, lazy[node])
    apply(node * 2 + 1, right - middle, lazy[node])
    lazy[node] = 0.0


def update(node, left, right, query_left, query_right, value):
    if query_left <= left and right <= query_right:
        apply(node, right - left + 1, value)
        return
    push(node, left, right)
    middle = (left + right) // 2
    if query_left <= middle:
        update(node * 2, left, middle, query_left, query_right, value)
    if middle < query_right:
        update(node * 2 + 1, middle + 1, right, query_left, query_right, value)
    summation[node] = summation[node * 2] + summation[node * 2 + 1]
    squared[node] = squared[node * 2] + squared[node * 2 + 1]


def query(node, left, right, query_left, query_right):
    if query_left <= left and right <= query_right:
        return summation[node], squared[node]
    push(node, left, right)
    middle = (left + right) // 2
    result_sum = result_square = 0.0
    if query_left <= middle:
        result_sum, result_square = query(node * 2, left, middle, query_left, query_right)
    if middle < query_right:
        right_sum, right_square = query(node * 2 + 1, middle + 1, right, query_left, query_right)
        result_sum += right_sum
        result_square += right_square
    return result_sum, result_square


build(1, 1, n)
answers = []
for _ in range(operations):
    operation = input().split()
    kind, left, right = int(operation[0]), int(operation[1]), int(operation[2])
    if kind == 1:
        update(1, 1, n, left, right, float(operation[3]))
    else:
        count = right - left + 1
        total_value, total_square = query(1, 1, n, left, right)
        if kind == 2:
            answers.append(f"{total_value / count:.4f}")
        else:
            answers.append(f"{total_square / count - (total_value / count) ** 2:.4f}")
print("\n".join(answers))

原有 C++ 版本仍保留：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-16 23:46
 * update_at: 2026-07-16 23:46
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

建树 O(n)，每次操作 O(log n)，空间 O(n)。

总结

遇到方差查询，先把定义改写成一阶矩和二阶矩，区间加就能在线维护。