Algorithm

线段树-SegmentTree

线段树的优点:
  O(logn)时间内，在一段区间中求最大最小值

线段树的特征:

  • 二叉树

  • 每个节点表示一个区间的最大值

  • 左儿子 = 平分后左区间，右儿子 = 平分后右区间

  • 不可增减节点(线段数结点总数需要在最开始就给定)

  • 空间复杂度: O(n)

    • 线段树的操作:

    线段树的查询: O(logn)

  • 查询的区间 和 线段树节点区间 相等 -> 直接返回

  • 查询的区间 被 线段树节点区间 包含-> 递归向下搜索左右子树

  • 查询的区间 和 线段树节点区间 不相交 -> 结束

  • 查询的区间 和 线段树节点区间 相交且不相等 -> 分裂查询区间

    • 线段树的建立: O(n)

  • 自上而下递归分裂

  • 自下而上回溯更新

    • 线段树的更新: O(logn)

  • 自上而下递归查询

  • 自下而上回溯更新

    • 问题特征:

  • 对区间求sum

  • 对区间求Max/Min

  • 对区间求Count

    • 构建形式

    1. 下标作为建立区间
    2. 值作为建立区间

    Python:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    #!/usr/bin/env 
    # -*- coding:utf-8 -*-
    class SegmentTree(object):
        def __init__(self, nums, s=None, e=None): # build
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            n = len(nums)
            if s == None:
                self.start, self.end = 0, n-1
            else:
                self.start, self.end = s, e
            self.mid = self.start + (self.end-self.start)/2
            self.left, self.right = None, None
            self.val = 0
            if self.end < self.start:
                return
            if self.end == self.start:
                self.val = nums[self.start]
            else:
                self.left = SegmentTree(nums, self.start, self.mid)
                self.right = SegmentTree(nums, self.mid+1, self.end)
                self.val = self.left.val + self.right.val
            
        def update(self, i, val): # modify
            """
            :type i: int
            :type val: int
            :rtype: int
            """
            if i == self.start and i == self.end:
                self.val = val
            else:
                if i <= self.mid:
                    self.left.update(i, val)
                else:
                    self.right.update(i, val)
                self.val = self.left.val + self.right.val
            
        def sumRange(self, i, j): # query
            """
            sum of elements nums[i..j], inclusive.
            :type i: int
            :type j: int
            :rtype: int
            """
            if i == self.start and j == self.end: # equal
                return self.val
            elif self.start > j or self.end < i: # not intersect
                return 0
            else: # intersect
                if i > self.mid: # all at the right sub tree
                    return self.right.sumRange(i, j)
                elif j <= self.mid: # all at the left sub tree
                    return self.left.sumRange(i, j)
                else: # some at the right & some at the left
                    return self.left.sumRange(i, self.mid) + self.right.sumRange(self.mid+1, j)