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

#树状数组进阶（2） ###●前置知识：树状数组，如果没有学过请右转这篇文章：[传送门](https://blog.csdn.net/flushhip/article/details/79165701)。 ###●我的上一篇文章：[树状数组进阶1](https://www.luogu.org/blog/Chanis/super-BIT)，如果没有看过也没事，两篇文章关系不大。 ###●与上次相比，本文代码编译过了，但是如有错误还是请指出。 ###●QQ826755370 ##引入 -“平衡树好难写~~（背）~~啊，要是能像树状数组一样短就好了。” -“树状数组在某种程度上也可以代替平衡树的，我们来看看吧。” ##正文 ###建树/删除或增加一个数 -“既然完成的是平衡树的功能，那么建树应该和普通的树状数组不同吧？” -“是的，由于平衡树有个很重要的操作是查排名，所以我们设c[i]管理区域为a[i...j]，那么c[i]记录的则为数字i...j的数量和，这样查询排名时就可以直接用普通树状数组中求和的方法。” 没什么想说的了，上面那段话已经把建树方法说得很清晰了，需要注意的时a数组中只能有正整数，如果有负数和0请将a数组的所有元素同加1个数。如果a数组中的最大值特别大，我们则需要离散化（这个没人不会吧？），但是离散化的话树状数组就变成离线的了，这是树状数组代替平衡树的一个劣势，下面直接上代码（没有加离散化），如果要加一个数x写1，删除1个数x写-1。 ```cpp 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); } } ``` ###求排名 上面也已经将求排名的方法说了一遍，这里我也不说了吧...代码： ```cpp 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，超过了就退回去，否则就保存。 ```cpp 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)，后继同理，不再赘述，代码： ```cpp int pre(int x){ return findKth(myrank(x)-1); } int nxt(int x){ return findKth(myrank(x)+1); } ``` 以上就是树状数组代替平衡树的基本操作，下面我们来看几道题。 ##作业 1.[洛谷P3369 普通平衡树](https://www.luogu.org/problemnew/show/P3369) 不想说什么，裸题，就是把上面的东西结合在一起。 2.[洛谷P1486 郁闷的出纳员](https://www.luogu.org/problemnew/show/P1486) 一些小小的技巧，不难。 3.[洛谷P3285 方伯伯的OJ](https://www.luogu.org/problemnew/show/P3285) 开一个这种树状数组+map。 ###吐槽:谁把P3238的标签加了个平衡树啊...一点关系都没有吧...还有，这题为什么是黑题... ###Tips:树状数组并不能完全代替平衡树，树状数组不能做到翻转区间。 ##完结撒花！*★,°*:.☆(￣▽￣)/$:*.°★* 。