ConanKIDの小窝

ConanKIDの小窝

树状数组 学习笔记

posted on 2020-10-01 16:02:12 | under 学习笔记 |

1.引入

教练:我现在有一个序列,需要支持两种操作。第一个,对序列中的一个数进行修改;第二个,求出某个区间中的所有数之和。

我:线段树他不香吗$\mathcal{QwQ}$(一般教材上面是先讲了树状数组,但我是真的先学了线段树再学的树状数组)

教练:我们可以不用线段树,而是使用树状数组。它支持两种操作:单点修改和查询前缀和,一次操作的时间复杂度为$\mathcal O(\log n)$。它有两个好处:第一,常数小;第二,码量也小。

我(两眼放光):我早就厌烦线段树的$1.5\mathcal{KB}$码量了!

2. 查询前缀和

一般来说,要求出序列中前$k$个数的和,就要扫描整个区间,时间复杂度为$\mathcal O(k)$。

我们想想,为什么这种方法慢?当然是因为我们是一个一个数循环的。如果我们能够把整个区间分成若干个小区间,而这些小区间内的数之和我们都知道,不就能快速求出答案了吗?

我们知道,任何一个数都可以表示成唯一的二进制形式,也就是可以表示成若干个互不相同的二的幂次方之和。利用这个思想,可以把区间长度$k$分成若干个二的幂次方。设$k=2^{a_1}+2^{a_2}+\cdots+2^{a_t}$且$2^{a_1}>2^{a_2}>\cdots>2^{a_t}$,则区间$[1,k]$可以表示为区间长度依次为$2^{a_1},2^{a_2},\cdots,2^{a_t}$的$t$个小区间。

易知,以$r$结尾的小区间,长度为$r$在二进制表示下,最低位的$1$及后面的$0$构成的数值。

设一个数$x$在二进制表示下,最低位的$1$及后面的$0$构成的数值为$lowbit(x)$。结论:$lowbit(x)=x$&$(-x)$。

证明(摘自信息学竞赛一本通):

设$x$的第$k$位为$1$,$0$至$k-1$位均为$0$。先把$x$的所有位都取反,此时第$k$位变为$0$,第$0$至$k-1$位均为$1$。再令$x\gets x+1$,此时因为进位,第$k$位为$1$,第$0$至$k-1$位均为$0$。

在上面的取反加一操作后,$x$的第$k+1$位到最高位恰好与原数相反,而最低位到第$k$位与原数完全相同。所以,$n$&$($~$n+1)$就是我们最后的答案。而在补码表示下,~$n+1=-n$,所以:$lowbit(n)=n$&$(-n)$。

定义一个数组$sum$,$sum_i$表示以区间$[i-lowbit(i)+1,i]$内的数之和。那么我们在求前$k$个数的和时,只需要建立一个指针$x$和答案计数器$ans$,每次将$ans$加上$sum_x$,同时将$x$减去$lowbit(x)$,就可以利用上述思想,将$ans$分成至多$\log(k)$个小区间,快速的求出答案。

当然,如果求的不是前$k$个数的和,而是一个随机的区间,那么只要用两个前缀和相减就可以了。

int query(int x){//表示查询前x个数的和
    int ans=0;
    while(x){
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}

3. 单点修改

单点修改可以看做是前缀和查询的一个逆运用。

考虑$a_k$的值变化后,需要将哪些$sum_x$更新。

首先,如果$x_1-lowbit(x_1)=k$,那么显然要更新$sum_{x_1}$。此时$x_1$显然等于$k+lowbit(k)$。

同理,$sum_{x_1}$的值更新后,若$x_2-lowbit(x_2)=x_1$,也要将$sum_{x_2}$更新。

以此类推,将$x$不断地加上$lowbit(x)$,整个过程中得到的数对应的$sum$都要被更新。

我们运用反向思维,成功解决了单点修改。

void update(int x,int val){//表示把a[x]加上val
    while(x<=n){
        sum[x]+=val;整个过程中得到的x都要被更新
        x+=lowbit(x);
    }
}

4. 收尾

经过上述操作,我们已经可以解决区间查询和单点修改的问题了。

分析易得,两种操作的时间复杂度均至多为$\mathcal{O}(\log n)$。一般情况下,都可以把一次操作的时间看成一个小常数。这和线段树比起来,已经可以说很优秀啦。

而且,树状数组的代码量果然不长,在本人的码风下,只有短短的$550$个字节。

下面以模板题P3374为例,附上完整代码。

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