[hero planet July training leetcode problem solving daily] 24th line segment tree

daily

subject

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

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

1. Title Description

2. Thought analysis

• This problem can be line segment tree 、 Tree array 、 Merger 、 Ordered set .
• I test the fastest ordered set .
• No data range is given, so it needs to be discretized .
• Can you do it if you don't want to discretize , Can also do , Be coquettish ： Observe what the code passes in int, Actual data range [-2^31 , 2^31-1], We'll use a segment tree , We have to turn them all into [1,N] Number between , So we all add 2^32, The maximum value of the segment tree is 2^33, In this way, it can be opened dynamically ！

3. Code implementation

class IntervalTree:
    def __init__(self, size,nums=None):
        self.size = size
        self.nums = nums
        self.interval_tree = collections.defaultdict(int)
        if nums:
            self.build_tree(1,1,size)

    def build_tree(self,p,l,r):
        interval_tree = self.interval_tree
        nums = self.nums
        if l == r:
            interval_tree[p] = nums[l-1]
            return
        mid = (l+r)//2
        self.build_tree(p*2,l,mid)
        self.build_tree(p*2+1,mid+1,r)
        interval_tree[p] = interval_tree[p*2]+interval_tree[p*2+1]
    
    def add_point(self,p,l,r,index,add):        
        if index < l or r < index:
            return 
        interval_tree = self.interval_tree
        interval_tree[p] += add
        if l == r:
            return
        mid = (l+r)//2
        if index <= mid:
            self.add_point(p*2,l,mid,index,add)
        else:
            self.add_point(p*2+1,mid+1,r,index,add)
    
    def sum_interval(self,p,l,r,x,y):        
        if y < l or r < x:
            return 0
        interval_tree = self.interval_tree
        if x<=l and r<=y:
            return interval_tree[p]
        mid = (l+r)//2
        s = 0
        if x <= mid:
            s += self.sum_interval(p*2,l,mid,x,y)
        if mid < y:
            s += self.sum_interval(p*2+1,mid+1,r,x,y)
        return s

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        #  discretization 
        # hashed = sorted({*nums})
        size = 2**33
        #  Segment tree statistical reverse pair 
        tree = IntervalTree(size)
        ans = 0
        for i in range(n - 1, -1, -1):
            # pos = bisect_left(hashed,nums[i])+1
            ans += tree.sum_interval(1,1,size,1,nums[i]-1+2**32)
            tree.add_point(1,1,size,nums[i]+2**32,1)
        return ans