Mô phỏng thuật toán Cây phân đoạn (Segment Tree)

Segment Tree · Nhóm: Cấu trúc dữ liệu

Cây phân đoạn (Segment Tree) (Segment Tree), nhóm Cấu trúc dữ liệu.

Mã Python

def build(node):                 # node = range [lo, hi]
    if node.lo == node.hi:        # leaf
        node.sum = a[node.lo]
        return node.sum
    L = build(node.left)
    R = build(node.right)
    node.sum = L + R
    return node.sum

def query(node, l, r):
    if node.hi < l or node.lo > r:   # outside range
        return 0
    if l <= node.lo and node.hi <= r: # fully covered
        return node.sum
    return query(node.left, l, r) + query(node.right, l, r)

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.