Problem Description

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Problem Link

Solution 1: Segment Tree

we can use segment tree to solve this issue. The key point is how to build the segment tree.

Here are some Key Points:

1.Transform the problem: Instead of checking nums[i] > 2*nums[j] directly, we store 2*nums[j] values and query how many < nums[i].

2.Process order matters: Right-to-left ensures we only consider valid pairs where i < j.

3.Coordinate compression: Maps potentially huge value ranges to manageable array indices.

Code

type SegmentTree struct {
    tree []int
    n int
}

func NewSegmentTree(size int) *SegmentTree {
    return &SegmentTree{
        tree: make([]int, 4*size),
        n: size,
    }
}

func (st *SegmentTree) update(node, start, end, idx int) {
    if start == end {
        st.tree[node]++
    } else {
        mid := (start + end) / 2
        if idx <= mid {
            st.update(2*node+1, start, mid, idx)
        } else {
            st.update(2*node+2, mid+1, end, idx)
        }
        st.tree[node] = st.tree[2*node+1] + st.tree[2*node+2]
    }
}

func (st *SegmentTree) query(node, start, end, l, r int) int {
    if r < start || l > end  {
        return 0
    }
    if l <= start && end <= r {
        return st.tree[node]
    }
    mid := (start + end) / 2
    return st.query(2*node+1, start, mid, l, r) + st.query(2*node+2, mid+1, end, l, r)
}

func (st *SegmentTree) Update(idx int) {
    st.update(0, 0, st.n-1, idx)
}

func (st *SegmentTree) Query(l, r int) int {
    if l > r {
        return 0
    }
    return st.query(0, 0, st.n-1, l, r)
}

func reversePairs(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }
    allValues := make([]int, 0, len(nums)*2)
    for _, v := range nums {
        allValues = append(allValues, v)
        if v > 0 && v <= (1<<31-1)/2 {
            allValues = append(allValues, 2*v)
        } else if v < 0 && v >= -(1<<31)/2 {
            allValues = append(allValues, 2*v)
        } else if v == 0 {
            allValues = append(allValues, 0)
        } else {
            if nums > 0 {
                allValues = append(allValues, 1<<31-1)
            } else {
                allValues = append(allValues, -(1<<31))
            }
        }
    }
    sort.Ints(allValues)
    compressed := removeDuplicates(allValues)
    
    valueToIndex := make(map[int]int)
    for i, v := range compressed {
        valueToIndex[v] = i
    }
    
    st := NewSegmentTree(len(compressed))
    result := 0
    for i := len(nums) -1; i >= 0; i-- {
        targetIndex := firstGreaterIdx(compressed, nums[i])
        if targetIndex > 0 {
            result += st.Query(0, targetIndex-1)
        }
        doubleVal := 2 * nums[i]
        
        var insertVal int
        if nums[i] > 0 && nums[i] <= (1<<31-1)/2 {
			insertVal = doubleVal
		} else if nums[i] < 0 && nums[i] >= (-(1<<31))/2 {
			insertVal = doubleVal
		} else if nums[i] == 0 {
			insertVal = 0
		} else {
			if nums[i] > 0 {
				insertVal = 1<<31 - 1
			} else {
				insertVal = -(1 << 31)
			}
		}
		insertIdx := valueToIndex[insertVal]
        st.Update(insertIdx)
    }
    return result
}

func firstGreaterIdx(nums []int, target int) int {
    left, right := 0, len(nums)
    
    for left < right {
        mid := (left + right) / 2
        if nums[mid] <= target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

func removeDuplicates(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    result := []int{nums[0]}
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            result = append(result, nums[i])
        }
    }
    return result
}

Time Complexity: O(nlogn)

Space Complexity: O(n)