可以代替平衡树的树状数组?——树状数组进阶(2)

2018-08-02 17:18:10


树状数组进阶(2)

●前置知识:树状数组,如果没有学过请右转这篇文章:传送门

●我的上一篇文章:树状数组进阶1,如果没有看过也没事,两篇文章关系不大。

●与上次相比,本文代码编译过了,但是如有错误还是请指出。

●QQ826755370

引入

-“平衡树好难写(背)啊,要是能像树状数组一样短就好了。”

-“树状数组在某种程度上也可以代替平衡树的,我们来看看吧。”

正文

建树/删除或增加一个数

-“既然完成的是平衡树的功能,那么建树应该和普通的树状数组不同吧?”

-“是的,由于平衡树有个很重要的操作是查排名,所以我们设c[i]管理区域为a[i...j],那么c[i]记录的则为数字i...j的数量和,这样查询排名时就可以直接用普通树状数组中求和的方法。”

没什么想说的了,上面那段话已经把建树方法说得很清晰了,需要注意的时a数组中只能有正整数,如果有负数和0请将a数组的所有元素同加1个数。如果a数组中的最大值特别大,我们则需要离散化(这个没人不会吧?),但是离散化的话树状数组就变成离线的了,这是树状数组代替平衡树的一个劣势,下面直接上代码(没有加离散化),如果要加一个数x写1,删除1个数x写-1。

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

求排名

上面也已经将求排名的方法说了一遍,这里我也不说了吧...代码:

int myrank(int x){//rank为c++11关键字 
    int res=1;x--;//等于1是因为还要算上自己,x--将自己排除在外,主要是防止有几个和自身相等的数 
    while(x) res+=c[x],x-=lowbit(x);
    return res; 
}

现在你已经会用树状数组求逆序对个数了,当插入了一个i时,询问myrank(i-1),所有的myrank(i-1)之和即为逆序对个数,代码就不写了。

求K小值

以下内容可能稍稍难以理解,我们放一张树状数组的图,边看边对照:

树状数组

这里用到了倍增算法, 当我们把c[i]的下标加上2^k后,c[i+2^k]的值就是我们增加的这一段区间元素的个数。就可以直接判断当前元素个数是否超过了K,超过了就退回去,否则就保存。

int findKth(int k){
    int ans=0,cnt=0;
    for(int i=30;i>=0;i--){//i实际上为log2(maxn),maxn是a数组中的最大值
        ans+=(1<<i);
        if(ans>maxn || cnt+c[ans]>=k)ans-=(1<<i);//>=k是为了防止有重复元素
        else cnt+=c[ans];
    }
    return ++ans;//如果找不到则返回n+1
}

前驱后继

我们不难发现,x的前驱pre(x)=findKth(myrank(x)-1),后继同理,不再赘述,代码:

int pre(int x){
    return findKth(myrank(x)-1);
}
int nxt(int x){
    return findKth(myrank(x)+1);
}

以上就是树状数组代替平衡树的基本操作,下面我们来看几道题。

作业

1.洛谷P3369 普通平衡树 不想说什么,裸题,就是把上面的东西结合在一起。

2.洛谷P1486 郁闷的出纳员 一些小小的技巧,不难。

3.洛谷P3285 方伯伯的OJ 开一个这种树状数组+map。

吐槽:谁把P3238的标签加了个平衡树啊...一点关系都没有吧...还有,这题为什么是黑题...

Tips:树状数组并不能完全代替平衡树,树状数组不能做到翻转区间。

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