Java Segment Tree Solution


  • 1

    Inspired by binary index tree solution, I just wrote a segment tree version.

    public class Solution {
    	int n;
    	int[] nums;
    	int[] numsSorted;
    	int[] segmentTree;
    	public int reversePairs(int[] nums) {
    		n = nums.length;
    		nums = nums;
    		numsSorted = Arrays.copyOf(nums, n);
    		Arrays.sort(numsSorted);
    		segmentTree = new int[n * 2];
    
    		int res = 0;
    		for (int val : nums) {
    			res += search(findIndex(2L * val + 1));
    			update(findIndex(val));
    		}
    		return res;
    	}
    
    	private int findIndex(long val) {
    		int l = 0, r = n - 1;
    		while (l <= r) {
    			int mid = l + (r - l) / 2;
    			if (numsSorted[mid] >= val) {
    				r = mid - 1;
    			} else {
    				l = mid + 1;
    			}
    		}
    		return l;
    	}
    
    	private int search(int pos) {
    		int l = pos + n;
    		int r = n * 2 - 1;
    		int sum = 0;
    		while (l <= r) {
    			if (l % 2 == 1) {
    				sum += segmentTree[l];
    				l++;
    			}
    			if (r % 2 == 0) {
    				sum += segmentTree[r];
    				r--;
    			}
    			l /= 2;
    			r /= 2;
    		}
    		return sum;
    	}
    
    	private void update(int pos) {
    		pos += n;
    		segmentTree[pos] += 1;
    		while (pos > 0) {
    			int l = pos;
    			int r = pos;
    			if (pos % 2 == 0) {
    				r = pos + 1;
    			} else {
    				l = pos - 1;
    			}
    			segmentTree[pos / 2] = segmentTree[l] + segmentTree[r];
    			pos /= 2;
    		}
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.