原題

對于一棵 最大線段樹, 每個節(jié)點包含一個額外的 max 屬性，用于存儲該節(jié)點所代表區(qū)間的最大值。
設計一個 modify 的方法，接受三個參數(shù) root、 index 和 value。該方法將 root 為跟的線段樹中 [start, end] = [index, index] 的節(jié)點修改為了新的 value ，并確保在修改后，線段樹的每個節(jié)點的 max 屬性仍然具有正確的值。

對于線段樹:

                      [1, 4, max=3]
                    /                \
        [1, 2, max=2]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]

如果調(diào)用 modify(root, 2, 4), 返回:

                      [1, 4, max=4]
                    /                \
        [1, 2, max=4]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]

或 調(diào)用 modify(root, 4, 0), 返回:

                     [1, 4, max=2]
                    /                \
        [1, 2, max=2]                [3, 4, max=0]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]

解題思路

• 自上而下，遞歸查找
• 自下而上，回溯更新

完整代碼

"""
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, index, value: The root of segment tree and 
    @ change the node's value with [index, index] to the new given value
    @return: nothing
    """
    def modify(self, root, index, value):
        if root.start == index and root.end == index:
            root.max = value
            return
            
        mid = (root.start + root.end) / 2
        if root.start <= index and index <= mid:
            self.modify(root.left, index, value)
        elif mid < index and index <= root.end:
            self.modify(root.right, index, value)
        root.max = max(root.left.max, root.right.max)