P3372 题解

sunqihuan · 2024-08-13 21:11:47 · 题解

用树状数组解决，最短代码挑战

~~众所周知~~，树状数组可以解决单值修改区间求和，或是区间修改单值查询的问题

可你们不知道的是，树状数组使用黑科技以后可以实现线段树的大部分功能！

本文将从树状数组的诞生讲起……

树状数组的基本使用

（大佬请自动跳过）

~~我无意给大家介绍这个没用的东西~~

说实话，还是有一点点用的，就是它的代码长度比接下来的线段树少亿点点。

问题

首先，说一下树状数组的基本作用。

可以求区间修改，单值查询，或单点修改,区间求和，只能处理差分性质的问题

铺垫

前缀和：

s_n=\sum_{i=1}^n a_i

差分：

c_n=a_n-a_{n-1}

满足性质：

\sum_{i=1}^{n} c_i=a_n

二进制下从右到左第一次出现 $1$ 时这一位的权值。求法：$lowbit(x)=x&(-x)

定义状态

我们将数组 a 的每一个元素的和 a_i 求出来，很明显这种情况下我们求和是 T(n) 的。

我们想要加速，所以我们把相邻两个元素合并成一个，即 a_1+a_2 当成一个元素，a_3+a_4 当成一个元素，这样求和，是 T(\frac {n}{2})。

……

极限分割下，我们求和的时间复杂度是 O(log_2 n)

存贮

接下来，我们考虑一下如何存贮这些东西。

根据二进制唯一分解定理我们可以知道，按如下方法我们一定可以求出所有区间的和：

c_1=a_1

c_2=a_1+a_2

c_3=a_3

c_4=a_1+a_2+a_3+a_4

c_5=a_5

…

求和

因为：

\sum_{i=l}^{r} a_i=\sum_{i=1}^{r} a_i-\sum_{i=1}^{l-1} a_i

所以我们可以求\sum_{i=1}^{n'} a_i 的值。

列出每个数的二进制和对应的求和关系：

n'=1

(n')_2=1

\sum_{i=1}^{n'}=c_1

n'=2

(n')_2=10

\sum_{i=1}^{n'}=c_2

n'=3

(n')_2=11

\sum_{i=1}^{n'}=c_2+c_3

规律应该很好找，就是每一次加上 c_x，减去 x 的 lowbit，直到 x 为 0。

修改

将 x 加上 k，我们要修改什么元素呢？

当然是修改包含 x 的元素了。不难发现，包含 x 的元素就是从 x 开始，一直加上 x 的 lowbit，直到 x 的最大值。

注意，树状数组只能实现加的操作，没法实现改变的操作。要是把 x 强行设定为 y，相当于 x 加上 y-x。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],c[100005],m,p,x,y; 
int lowbit(int x){
    return x&(-x);
}
void updata(int x,int y){
    int k=x;
    while(k<=n){
        c[k]+=y;
        k+=lowbit(k);
    }
}
int getsum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        updata(i,a[i]);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>p>>x>>y;
        if(p==1){
            updata(x,y);
        }else{
            cout<<getsum(y)-getsum(x-1)<<endl;
        }
    }
    return 0;
}

树状数组的扩展

树状数组能解决线段树能解决的大部分问题，但是它的扩展性能还是没有线段树强。

区间修改单值查询

要是没有时间限制，肯定是用差分。用差分的话就可以用修改两个点的方式实现区间修改，用一遍循环实现单值查询……

等等，这怎么这么眼熟？？？

没错，区间修改单值查询的情况就可以转化为差分数组的单点修改区间求和，然后就没了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],c[100005],m,p,x; 
int lowbit(int x){
    return x&(-x);
}
void updata(int x,int y){
    int k=x;
    while(k<=n){
        c[k]+=y;
        k+=lowbit(k);
    }
}
int getsum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
        updata(i,b[i]);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>p>>x;
        if(p==1){
            int y,l;
            cin>>y>>l;
            updata(x,l);
            updata(y+1,-l);
        }else{
            cout<<getsum(x)<<endl;
        }
    }
    return 0;
}

区间修改区间查询

~~哎，这不是线段树干的么？~~

好吧，树状数组也能干。

根据上面的理论，区间修改我们可以用差分数组实现。那么区间求和呢？

\sum_{i=1}^{k} a_i=\sum_{i=1}^{k}\sum_{j=1}^{i} d_j

=\sum_{i=1}^{k}d_i\times (k-i+1)

=(k+1)\times \sum_{i=1}^{k} d_i-\sum_{i=1}^{k} i\times d_i

所以我们只需要维护两个树状数组，分别维护 d_i 和 i \times d_i 即可。

而查询时仅需两次查询作差即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T,a[100005],c1[100005],c2[100005]; 
int lowbit(int x){
    return x&(-x);
}
void update(int x,int k){
    int t=x;
    while(x<=n){
        c1[x]+=k;
        c2[x]+=t*k;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0,t=x;
    while(x>0){
        ans=ans+(t+1)*c1[x]-c2[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main(){
    cin>>n>>T;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        update(i,a[i]-a[i-1]);
    }
    while(T--){
        int op;
        cin>>op;
        if(op==1){
            int x,y,k;
            cin>>x>>y>>k;
            update(x,k);
            update(y+1,-k);
        }else{
            int x,y;
            cin>>x>>y;
            cout<<sum(y)-sum(x-1)<<endl;
        }
    }
    return 0;
}

提交记录

目前没有发现代码更短的，有发现的大佬可以私信我。