lintcode249. 统计前面比自己小的数的个数

这道题应用到了BIT， binary indexed tree
lintcode

首先建立BIT，关于BIT， 这里介绍一个YouTube印度大神的视频，非常清晰易懂链接, 建议翻墙查看

image.png

这里我大致讲一下，其中s1代表a[1,1], s2代表a[1,2], s4代表a[1,4], s8代表a[1,8]
s3代表a[3,3]， s5=a[5,5], s6 = a[5,6], s7 = a[7,7], 这里的a[i, j ]为范围

在建立树的时候，如果a[1]加入树，那么要一次更新s1, s2, s4, s8
如果是a3, 则一次更新s4, s8， 上图的路径可以看做修改的路径
关系为int i = index; i < s.length; i = i + i&(-i)

而在查询的时候，如果查询前7个的sum， 那么要累加s7, s6, s4
关系为 int i = index; i > 0; i = i - i&(-i)

关于这道题，首先现将这个array序列化，即每个位置是其相对的大小的位置，这样可以减少bit的空间浪费

然后遍历数组，在BIT插入当前数，并在BIT查询比它小的数的数目，这里BIT的value代表某个数出现了几次
代码如下，时间复杂度为O(nlgn)

public class Solution {
    /**
     * @param A: an integer array
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    public List<Integer> countOfSmallerNumberII(int[] A) {
        // write your code here
         List<Integer> res = new ArrayList<>();
        int[] bits = new int[A.length + 1];
        serialization(A);
        
        for(int i = 0; i < A.length; i++){
            
            System.out.println("av");
            increase(bits, A[i]);
            res.add(getSum(bits, A[i] - 1));
        }
        
        return res;
    }
    //序列化数组
    private void serialization(int[] A){
        int[] sort = A.clone();
        Arrays.sort(sort);
        for(int i = 0; i <A.length; i++){
            A[i] = Arrays.binarySearch(sort, A[i]) + 1;
            System.out.println(A[i]);
        }
        
    }
    //添加操作
    private void increase(int[] bits, int index){
        for(int i = index; i < bits.length; i = i + (i&(-i))){
            bits[i]++;
        }
    }
    //查询操作
    private int getSum(int[]bits, int index){
        int sum = 0;
        for(int i = index; i > 0; i= i - (i&(-i))){
            sum += bits[i];
        }
        return sum;
    }
    
   
}