当前位置：网站首页>[brother hero June training] day 25: tree array

Tree array or binary index tree （ English ：Binary Indexed Tree）, Named after its inventor Fenwick Trees , The earliest by Peter M. Fenwick On 1994 In the past years A New Data Structure for Cumulative Frequency Tables The title is published in SOFTWARE PRACTICE AND EXPERIENCE. Its original intention is to solve the cumulative frequency in data compression （Cumulative Frequency） The calculation of , Now it is mostly used to efficiently calculate the prefix and , Interval and .

One 、 Flip it right

493. Flip it right

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;
    }
}

Two 、 Reverse pairs in arrays

The finger of the sword Offer 51. Reverse pairs in arrays

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;
    }
}