可以代替线段树的树状数组?——树状数组进阶(1)

2018-07-30 09:57:56


树状数组进阶(1)

  • 前置知识:树状数组,如果没有学过请右转这篇文章:传送门,前缀和,差分。
  • 本文代码均未经编译,如有错误请指出。
  • QQ826755370

引入

大家学了线段树与树状数组后,一定会觉得树状数组比线段树好写(背)多了,常数也小多了(分析lowbit操作,每次操作中每个节点被访问的概率是1/2,所以常数是1/2)但是美中不足的是树状数组不能区间修改+区间查询啊。事实上,树状数组可以做到这些,还可以查询第k大(小)值。

1、最简单的单点修改+区间查询

这个就不要我讲了吧,直接上代码:

void add(int pos,int x){
    while(pos<=n) c[pos]+=x,pos+=lowbit(pos);
}
int getsum(int pos){
    int sum=0;
    while(pos) sum+=c[pos],pos-=lowbit(pos);
    return sum;
}

2、 稍微难一点点的区间修改+单点0查询

这里用的是差分的思想。

我们设原数组为a,则我们需要维护一个差分数组delta: $delta[i]=a[i]-a[i-1]$

那么我们可以得到: $a[i]=\sum_{j=1}^idelta[j]$

现在a[i]被表达成了一个数组内连续的几个元素的,这样我们就解决了查询的问题,那么我们该如何修改呢?

当我们需要将区间[l,r]上的每个数都加上x时,因为d数组是个差分数组,所以我们可以直接在树状数组上将delta[l]加上x,delta[r+1]减去x即可,代码如下:

void add(int pos,int x){
    while(pos<=n) delta[pos]+=x,pos+=lowbit(pos);
}
void modify(int l,int r,int x){
    add(l,x),add(r+1,-x);
}
int getsum(int pos){
    int sum=0;
    while(pos) sum+=delta[pos],pos-=lowbit(pos);
    return sum;
}

重点来了!

3、区间修改+区间查询

我们还是需要引入delta数组,这里的delta[i]表示区间a[i...j]都需要加上的值的和。那么当我们需要将区间[l,r]上的每个数都加上x时,我们还是可以直接在树状数组上将delta[l]加上x,delta[r+1]减去x。

那么问题来了,如何查询区间[l,r]的和?

我们设a[1...i]的和为sum[i],根据delta数组的定义,则:

$$sum[i]=\sum_{j=1}^ia[j]+\sum_{j=1}^idelta[j]*(i-j+1)$$ $$sum[i]=\sum_{j=1}^ia[j]+(i+1)*\sum_{j=1}^idelta[j]-\sum_{j=1}^idelta[j]*j$$

这样我们就不难看sum[i]是由哪三个部分组成的了。我们需要用一个asum数组维护a数组的前缀和,delta1与delta2两个树状数组,delta1维护delta数组的和,delta2维护delta[i]*i的和,代码如下:

void add(int *arr int pos,int x){
    while(pos<=n) arr[pos]+=x,pos+=lowbit(pos);
}
void modify(int l,int r,int x){
    add(d1,l,x),add(d1,r+1,-x),add(d2,l,x*l),add(d2,r+1,-x*(r+1));
}
int getsum(int *arr,int pos){
    int sum=0;
    while(pos) sum+=arr[pos],pos-=lowbit(pos);
    return sum;
}
int query(int l,int r){
    return asum[r]+r*getsum(d1,r)-getsum(d2,r)-(asum[l-1]+l*getsum(d1,l-1)-getsum(d2,l-1));
}

等等……线段树不是还能查最大最小值吗,事实上树状数组也能查。

4、区间最值

哦,我知道了,我来建树:

void build(){
    for(int i=1;i<=n;i++){
        cin>>a[i];int pos=i;
        while(pos<=n) c[pos]=max(c[pos],a[i]),pos+=lowbit(pos);
    }
}

如果你是这么写的,那么恭喜你……写错了。

以下内容有些难理解,先放一张图:

真正的树状数组

我们回想一下,当初刚学树状数组时为什么很多人总会说树状数组不能用来求最值。那是因为树状数组可以看作是一种前缀和,求和时可以用ans=ans[r]-ans[l-1]的性质,但是求最值无法满足这种减法的性质。分析一下我们刚才的代码,这么写也不是不对,而是每次查询前都必须初始化,时间复杂度难以接受,让我们换一种写法试一试:

void build(int n){
     for(int i=1;i<=n;i++){
          c[i]=a[i],int t=lowbit(i);
          for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
    }
}

现在更新完某个数,之前的元素的值都是正确的了,显而易见,建树的时间复杂度是O(nlogn)的。

那么我们该如何修改呢?当然不能在父亲节点上直接修改啦(手动滑稽),换了一种建树的方式就是为了维护c数组的正确性,修改同样也要保证c数组的正确性,那么在更新父亲节点时,我们就需要查询它所有的儿子节点,代码如下:

void add(int pos,int x){
    a[pos]=x;
    while(pos<=n){
        c[pos]=a[pos];int t=lowbit(i); 
        for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
        pos+=lowbit(pos);
    }
}

不难发现,每层循环都是lowbit操作,时间复杂度为O(王逸松)O(log(n)*log(n)),其实也没多慢,当n=1e5时,logn约等于16,就把一个logn当成常数看,线段树常数也挺大的啊,树状数组代码量还这么少。

修改是修改完了,那么问题来了,我们该如何查询?

假设当前查询的区间是[l,r],那么我们从r到l对每一个c数组的元素所控制的叶子节点进行判断。假设现在进行到了第i项,那么显然易得(看图):该数控制的a数组的元素是 [i-lowbit(i)+1,i]。设L=i-lowbit(i)+1,R=i。如果l<=L<=r那么就将c[L]加入最值的判断中,接着L--……,否则的话就只对第R个元素加入,然后R--……,代码如下:

int query(int l,int r){
    int ans=a[r];
    while(1){
        ans=max(ans,num[r]); if(r==l) break; r--;
        while(r-l>=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r);
        //while条件里面的 r-l怎么不写成r-l+1?这才是元素个数啊。
        //写r-l+1可能会跳到0,某位大佬试了一下,电脑蓝屏了。
        //我也没有试,刨根问底(想要作死)的同学可以自己试一下 
    }
    return ans;
}

显然,时间复杂度是 $O(logn*logn)$ 的。

完整代码如下:

void build(int n){
     for(int i=1;i<=n;i++){
          c[i]=a[i],int t=lowbit(i);
          for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
    }
}
void add(int pos,int x){
    a[pos]=x;
    while(pos<=n){
        c[pos]=a[pos];int t=lowbit(i); 
        for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
        pos+=lowbit(pos);
    }
}
int query(int l,int r){
    int ans=a[r];
    while(1){
        ans=max(ans,num[r]); if(r==l) break; r--;
          while(r-l>=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r);
    }
    return ans;
}

5、二维情况下的树状数组

  • 单点修改+区间查询 这个我并不想讲,唯一需要注意的点写在注释里了,直接上代码:

    void add(int x,int y,int z){
    int t=y;//注意这里需要使用一个变量保存y的值 
    while(x<=n){
        y=t;
        while(y<=n) c[x][y]+=z,y+=lowbit(y);
        x+=lowbit(x); 
    }
    }
    int getsum(int x,int y){
    int ans=0,t=y;
    while(x){
        y=t;
        while(y) ans+=c[x][y],y-=lowbit(y);
        x-=lowbit(x);
    }
    return ans;
    }
  • 区间修改+单点查询 在开始之前,我们先回想一下二维的前缀和如何求和:
    二维前缀和
    这个应该没什么问题吧?
    $$sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]$$ 那么我们和一维情形一样,开一个差分数组delta。 $$delta[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$$ 思路到此结束,希望大家可以自己写代码。

  • 区间修改+区间查询 这里只给出一句话思路,希望大家自己思考,写出代码。
    $$\sum_{i=1}^x\sum_{j=1}^ya[i][j]=\sum_{i=1}^x\sum_{j=1}^y\sum_{k=1}^i\sum_{l=1}^jdelta[k][l]$$
    思路:将以上式子变形成类似一维情形下最终得到的式子。

  • 区间最值 有这么毒瘤的题目吗……

完结撒花!★,°:.☆( ̄▽ ̄)/$:.°★

我的下一篇文章:可以代替平衡树的树状数组?——树状数组进阶(2)