线段树的查询_线段树查询

题目描述：对于一个有n个数的整数数组，在对应的线段树中, 根节点所代表的区间为0-n-1, 每个节点有一个额外的属性max，值为该节点所代表的数组区间start到end内的最大值。

为SegmentTree设计一个 query 的方法，接受3个参数root, start和end，线段树root所代表的数组中子区间[start, end]内的最大值。

样例：对于数组 [1, 4, 2, 3], 对应的线段树为：

query(root, 1, 1), return 4

query(root, 1, 2), return 4

query(root, 2, 3), return 3

query(root, 0, 2), return 4

在做此题之前，应该先完成“线段树的构造”这道题（详见：点击打开链接）。了解线段树的基本结构和递归构造线段树的方法。

此处，我默认所有看这道题题解的人都清楚线段树是如何构造的。也就是上面的链接中的问题。

然后，我们来看线段树的查询问题，我们按查询区间对线段树的每个节点来分析。对一个节点的查询不过也就是三种情况：

1. 节点为空，或者查询区间和节点区间完全没有交集：比如查询[0, 2]，而此时查询的节点是[3, 3]，那就是说查询是无效的，直接返回空（相当于是“剪枝”）

2. 查询区间包含了节点区间：比如查询区间是[0, 2]，而某个节点的区间是[0, 1]，那么查询对于这个节点的最大值，当然就是这个节点的最大值（max值）

3. 查询区间和节点区间有交集，单查询区间没有完全包含节点区间：比如，查询[1, 2]，初始时，查到根节点，发现跟根节点有交集，但不包含根节点。那我们就分别再查询根节点的左右孩子，对根节点的左右孩子也采取1~3步的措施，将取查询结果取最大值，就是最终的结果。

由第3步可以非常清楚地看出是递归的思路。

代码如下：

"""
Definition of SegmentTreeNode:
class SegmentTreeNode:
    def __init__(self, start, end, max):
        self.start, self.end, self.max = start, end, max
        self.left, self.right = None, None
"""
 
class Solution: 
    # @param root, start, end: The root of segment tree and 
    #                          an segment / interval
    # @return: The maximum number in the interval [start, end]
    def query(self, root, start, end):
 
        # case1: 节点为空或者查询区间和节点区间完全没有交集，返回空
        if root is None or root.start > end or root.end < start:
            return
 
        # case2: 查询区间包含了节点区间，最大值当然就是节点的最大值
        elif root.start >= start and root.end <= end:
            return root.max
 
        # case3: 查询区间和节点区间的一部分相交，则分别查询此节点的左右孩子
        else:
            return max(self.query(root.left, start, end), self.query(root.right, start, end))
        # write your code here