构建线段树时是否需要检查是否 lo > hi

Question

下面的代码是流行的线段树代码的稍微修改版本。

我的问题是为什么我们需要在递归构建树时进行 lo > hi 检查，我想不出 lo 永远大于 hi 的例子，因为在任何时候它们都等于 [2,2 ] 递归不会再深入了。

class SegmentNode:

  def __init__(self, start, end):

    self.value = 0
    self.start = start
    self.end = end
    self.left = None
    self.right = None

class SegmentTree:

  def __init__(self, nums):

    self.root = self.buildTree(nums, 0, len(nums)-1)


  def buildTree(self, nums, lo, hi):

    if lo > hi:
      return None

    if lo == hi:
      curr = SegmentNode(lo, hi)
      curr.value = nums[lo]
      return curr

    mid = (lo + hi)//2

    curr = SegmentNode(lo, hi)
    curr.left = buildTree(lo, mid)
    curr.right = buildTree(mid+1, hi)

    curr.value = curr.left.value + curr.right.value

    return curr

Answer 1

I cannot think of an example where lo will ever be greater than hi

  def __init__(self, nums):

    self.root = self.buildTree(nums, 0, len(nums)-1)


  def buildTree(self, nums, lo, hi):

    if lo > hi:
      return None

一个例子是：

如果一个空列表作为 nums 传递给 __init__，则 buildTree 被调用，0 作为 lo，-1 作为 hi。

构建线段树时是否需要检查是否 lo > hi

Do I need to check if lo > hi when building a segment tree

python

algorithm

tree

segment-tree