P1471 方差

Tooler_Yang · 2023-01-27 11:58:54 · 个人记录

这道题其实可以用树状数组来做。（线段树太板了，没有思维含量）

树状数组是用于单点修改，区间查询，或者区间修改，单点查询。 而这道题目是区间修改，区间查询。

所以我们要使用差分来转化。

例如 a:\{1,3,4,3,5\},那么它的差分序列就是 b:\{1,2,1,-1,2\}。

实现方式就是 b_i=a_i-a_{i-1}，如果有差分数组 b，那么有 a_i=\sum\limits_{j=1}^{i}b_j

那有什么好处？

还是那个 a 数组，假如需要将 [2,4] 之间的数都增加 2，那相应的，可以将 b 数组中 b_1 的值减 1，再把 b_4 的值加 1，就可以达到同样的效果。

那么如果在 a 数组中不管改变长度为多少的区间，在差分数组 b 中只需要更新两个数即可。

代码如下：

int lowbit(int x){return x&(-x);}
void add(int p,int x){
    while(p<=n){
        d[p]+=x;
        p+=lowbit(p);
    }
}
int sum(int x){
    long long ans=0;
    while(x){
        ans+=d[x];
        x-=lowbit(x);
    }
    return ans; 
}
int main(){
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=m;i++){
        int a;
        cin>>a;
        if(a==1){
            int b,c,d;
            cin>>b>>c>>d;
            add(b,d);
            add(c+1,-d);
        }
        else if(a==2){
            int x;
            cin>>x;
            cout<<b[x]+sum(x)<<"\n";
        }
    }

但是这只是区间查询，单点查找的代码，那如何查询区间呢？

那就一个一个查呗！

假设差分数组为 b，要求 a 数组在区间 [l,r] 的和，那所求的式子：

然而 b_i，i\cdot b_i 都是能通过树状数组来维护的。

代码如下：

int lowbit(int x){return x&(-x);}
void add(int p,int x){
    int u=p;
    while(p<=n){
        d[p]+=x;
        di[p]+=x*(u-1);
        p+=lowbit(p);
    }
}
int sum(int x){
    long long ans=0;
    int p=x;
    while(x){
        ans+=p*d[x]-di[x];
        x-=lowbit(x);
    }
    return ans; 
}
int get_sum(int l,int r){
    return sum(r)-sum(l-1);
}

那么在区间 [l,r] 之间的平均数就只要再除以 (r-l+1) 即可。

设区间 [l,r] 之间的平均数为 \bar{a}，区间长 r-l+1=n。那方差就是：

只要再直接用树状数组维护 a_i^2 即可。

再设 \sum\limits_{i=1}^{k} a_i=S_k，运用阿贝尔变换

然后就只要维护 (a_k-a_{k+1})a_k 就可以了，（(a_k-a_{k+1})ia_k 同理），就会发现 (a_k-a_{k+1}) 就是差分。

可是差分涉及到了两个值 a_k 和 a_{k+1}，所以如果要修改时就要分两种情况，同时设 (a_k-a_{k+1})a_k=A_k：

• 两个数都增加了 p，那 A_k 就会增加 p(a_k-a_{k+1})

• 如果这只有一个数增加了 p，如果是 a_k 增加了 p，A_k 就会增加 (2a_k-a_{k+1}+p)p，如果是 a_{k+1} 增加了 p，那A_k 就会增加 pa_k

其实就是要实现一个数组 P 使得 P_i=\sum\limits_{j=1}^{i}A_j

则有 P 的树状数组：

只能说毫无规律（有可能算错）