セグメント木

segment_tree.py

class SegmentTree:
    """Iterative segment tree: point update and range sum in O(log n)."""

    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * self.n + list(values)
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        i = index + self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, left, right):
        """Sum of values[left:right] (half-open range)."""
        total = 0
        lo, hi = left + self.n, right + self.n
        while lo < hi:
            if lo & 1:
                total += self.tree[lo]
                lo += 1
            if hi & 1:
                hi -= 1
                total += self.tree[hi]
            lo //= 2
            hi //= 2
        return total


if __name__ == "__main__":
    tree = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
    print(tree.query(2, 6))  # 7 + 9 + 6 + 4 = 26
    tree.update(3, 0)
    print(tree.query(2, 6))  # 7 + 0 + 6 + 4 = 17
    print(tree.query(0, 8))  # 28

python segment_tree.py