当前位置：网站首页>【英雄哥六月集训】第 25天: 树状数组

树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和，区间和。

一、翻转对

493. 翻转对

class Solution {
    
    class BIT{
    
        int[] tree;
        int n;
        public BIT(int n){
    
            this.n = n;
            this.tree = new int[n+1];
        }

        public static int lowbit(int x){
    
            return x & (-x);
        }

        public void update(int x, int d){
    
            while( x<=n){
    
                tree[x] +=d;
                x += lowbit(x);
            }
        }

        public int query(int x){
    
            int ans = 0;
            while(x != 0){
    
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
        
    }
    public int reversePairs(int[] nums) {
    
        Set<Long> allNumbers = new TreeSet<Long>();
        for(int x:nums){
    
            allNumbers.add((long) x);
            allNumbers.add((long) x * 2);
        }
        Map<Long,Integer> values = new HashMap<Long, Integer>();
        int idx = 0;
        for(long x : allNumbers){
    
            values.put(x,idx);
            idx++;
        }

        int ret = 0;
        BIT bit = new BIT(values.size());
        for (int i = 0; i<nums.length; i++){
    
            int left = values.get((long) nums[i]*2), right=values.size()-1;
            ret +=bit.query(right+1)-bit.query(left+1);
            bit.update(values.get((long) nums[i]) +1,1);

        }
        return ret;
    }
}

二、数组中的逆序对

剑指 Offer 51. 数组中的逆序对

class Solution {
    
    class BIT{
    
        int[] tree;
        int n;
        public BIT(int n){
    
            this.n = n;
            this.tree = new int[n+1];
        }

        public static int lowbit(int x){
    
            return x & (-x);
        }

        public void update(int x){
    
            int d=1;
            while( x<=n){
    
                tree[x] +=d;
                x += lowbit(x);
            }
        }

        public int query(int x){
    
            int ans = 0;
            while(x != 0){
    
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
        
    }
    public int reversePairs(int[] nums) {
    
        int n=nums.length;
        int[] tmp = new int[n];
        System.arraycopy(nums,0,tmp,0,n);
        Arrays.sort(tmp);
        for(int i=0;i<n;i++){
    
            nums[i]= Arrays.binarySearch(tmp,nums[i])+1;
        }
        BIT bit = new BIT(n);
        int ans = 0;
        for(int i = n-1;i>=0;--i){
    
            ans += bit.query(nums[i]-1);
            bit.update(nums[i]);
        }
        return ans;
    }
}