8.17 - hard - 62

315. Count of Smaller Numbers After Self

这道题主要有两种解法：segment tree和mergesort，两种解法都要好好掌握才好！

方法1：利用segment tree，取array的最大值和最小值做为区间范围，然后记录当前范围内的count，从后往前loop整个序列，找到相应的区间以及count。如果数值过大则会TLE
方法2: 利用segment tree，取array的长度做为segment tree的区间，然后要把所有值求set然后排序，并且记录它们区间比如说[5,2, 6,1]，排序[1,2,5,6] 如果当前求2的时候，就是求[0,1]区间内所有元素的个数，如果求5的时候就是求[0,3]区间内所有元素的个数。然后从右到左依次1.计算元素个数，2.把元素加入到segment tree里面。
方法3: 利用mergesort的性质，在mergesort的merge阶段，每有一次swap就是要count一次。
方法4: 利用 index tree, index tree是啥我还不知道

方法1

class SegTreeNode(object):
    def __init__(self, min_val, max_val):
        self.min_val = min_val
        self.max_val = max_val
        self.count = 0
        self.left = None
        self.right = None

    @property
    def mid(self):
        return (self.max_val+self.min_val)/2
    
class Solution(object):
    def countSmaller(self, nums):
        res = []
        if not nums:
            return res
        min_val = min(nums)
        max_val = max(nums)
        root = self.build(min_val, max_val)

        for i in range(len(nums)-1, -1, -1):
            res = [self.find(nums[i], root)] + res
            self.add(nums[i], root)
            #print root.count, root.left.count, root.right.count

        return res
    
    def build(self, min_val, max_val):
        if min_val <= max_val:
            root = SegTreeNode(min_val, max_val)
            if min_val == max_val:
                return root
            root.left = self.build(min_val, root.mid)
            root.right = self.build(root.mid+1, max_val)
            return root
        else:
            return None
    
    
    def find(self, x, root):
        if not root:
            return 0

        if x > root.max_val:
            return root.count
        else:
            if x < root.mid:
                return self.find(x, root.left);
            else:
                return self.find(x, root.left) + self.find(x, root.right);
    
    def add(self, x, root):
        if x < root.min_val or x > root.max_val:
            return
       
        root.count += 1
        if root.min_val == root.max_val:
            return
        
        if x <= root.mid:
            self.add(x, root.left)
        else:
            self.add(x, root.right)

方法2

class SegmentTreeNode(object):
    def __init__(self, val, start, end):
        self.val = val
        self.start = start
        self.end = end
        self.left = None
        self.right = None


class SegmentTree(object):
    def __init__(self, n):
        self.root = self.build(0, n - 1)

    def build(self, start, end):
        if start > end:
            return None

        root = SegmentTreeNode(0, start, end)
        if start == end:
            return root

        mid = (start + end)/2
        root.left = self.build(start, mid)
        root.right = self.build(mid+1, end)
        return root

    def update(self, i, val, root): # 更新val在当前root区间内的值个数，也就是说如果val在root区间内，则root.val += 1
        if i < root.start or i > root.end:
            return root.val

        if i == root.start == root.end:
            root.val += val
            return root.val
        root.val = self.update(i, val, root.left) + self.update(i, val, root.right)
        return root.val

    def cal(self, start, end, root): # 求区间0 ～ x-1的值得个数
        if end < root.start or start > root.end:
            return 0

        if start <= root.start and end >= root.end:
            return root.val

        return self.cal(start, end, root.left) + self.cal(start, end, root.right)


class Solution(object):
    def countSmaller(self, nums):
        hashTable = {v: i for i, v in enumerate(sorted(set(nums)))}
        # print hashTable
        tree, r = SegmentTree(len(hashTable)), []
        for i in xrange(len(nums) - 1, -1, -1):
            r.append(tree.cal(0, hashTable[nums[i]] - 1, tree.root))
            tree.update(hashTable[nums[i]], 1, tree.root)
        return r[::-1]