树状数组的前置知识明天更新.下面讲如何利用板子解题,明天会解释树状数组的思想以及板子的由来.
树状数组可以进行单点修改和区间查询,复杂度都是nlogn.
先给大家讲讲树状数组求逆序对.
假设现在有一个长度为5的数组是.
a[5]={2,5,7,3,2}首先进行一次离散化.离散化我就不解释了(板子代码里有,ls()就没了).
离散化后数组变成了a[5]={1,3,4,2,1}.
那么我怎么求逆序对呢?总所周知,逆序对是i<j<k,a[i]>a[j]>a[k]这种形式的东西.那么假如这个数出现了一次,那我就在那个位子加1.
我模拟一下这个数组(不要在意细节),首先是a[i],先出现了一次,那么add(a[i],1);在a[i]的位子上+1,前面的逆序对数就是,ans+i-sum(a[i]).就是答案,因为前面是数组是0的,然后出现了一次,在对应位子+1,逆序对就是i-sum(a[i]);//前面比它大的