[英雄星球七月集训LeetCode解题日报] 第24日 线段树

日报

题目

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

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

1. 题目描述

2. 思路分析

• 这题可以线段树、树状数组、归并、有序集合。
• 我测试有序集合最快。
• 没给数据范围因此要离散化。
• 如果不想离散化能做吗，也能做，下面骚一点：观察代码传入的是int，实际数据范围[-2^31 , 2^31-1]，我们要用线段树，得把它们都变成[1,N]之间的数,因此我们全部加上 2^32， 线段树最大值开成2^33, 这样就可以动态开点了！

3. 代码实现

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)
        # 离散化
        # hashed = sorted({*nums})
        size = 2**33
        # 线段树统计逆序对
        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