Giao diện
Segment Tree Operations
🎯 Mục tiêu
Luyện tập xây dựng Segment Tree, truy vấn tổng đoạn, cập nhật điểm và lazy propagation.
Mô tả bài tập
Segment Tree là cấu trúc dữ liệu hỗ trợ truy vấn và cập nhật trên đoạn trong O(log n). Bài tập này hướng dẫn từ xây dựng cơ bản đến lazy propagation.
Yêu cầu
Bài 1: Xây dựng Segment Tree
Xây dựng Segment Tree cho truy vấn tổng (range sum query) từ một mảng cho trước.
python
class SegmentTree:
def __init__(self, arr: list[int]):
# Xây dựng Segment Tree từ mảng arr
self.n = len(arr)
self.tree = [0] * (4 * self.n)
pass
def _build(self, node: int, start: int, end: int, arr: list[int]):
# Xây dựng cây đệ quy
pass
st = SegmentTree([1, 3, 5, 7, 9, 11])Bài 2: Range Sum Query
Thêm phương thức truy vấn tổng các phần tử trong đoạn [l, r].
python
def query(self, l: int, r: int) -> int:
# Trả về tổng các phần tử từ chỉ số l đến r (inclusive)
pass
st = SegmentTree([1, 3, 5, 7, 9, 11])
assert st.query(1, 3) == 15 # 3 + 5 + 7
assert st.query(0, 5) == 36 # tổng toàn mảngBài 3: Point Update
Thêm phương thức cập nhật giá trị tại một vị trí.
python
def update(self, idx: int, val: int):
# Cập nhật arr[idx] = val
pass
st = SegmentTree([1, 3, 5, 7, 9, 11])
st.update(2, 10) # arr[2] = 10
assert st.query(1, 3) == 20 # 3 + 10 + 7Bài 4: Lazy Propagation
Mở rộng Segment Tree để hỗ trợ cập nhật tất cả phần tử trong đoạn [l, r] tăng thêm val.
python
class LazySegTree:
def __init__(self, arr: list[int]):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n)
def range_update(self, l: int, r: int, val: int):
# Tăng tất cả phần tử trong [l, r] thêm val
pass
lst = LazySegTree([1, 3, 5, 7, 9])
lst.range_update(1, 3, 10) # +10 cho vị trí 1,2,3
assert lst.query(1, 3) == 45 # (3+10) + (5+10) + (7+10)Phân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - Build | O(n) | O(n) |
| 2 - Query | O(log n) | O(log n) |
| 3 - Update | O(log n) | O(log n) |
| 4 - Lazy Update | O(log n) | O(n) |
Gợi ý
Gợi ý Bài 1
Nút lá chứa giá trị mảng. Nút cha = tổng hai con. Đệ quy từ gốc (node=1) phân đoạn [0, n-1].
Gợi ý Bài 2
Nếu [start, end] nằm hoàn toàn trong [l, r] → trả về tree[node]. Nếu giao một phần → đệ quy hai con.
Gợi ý Bài 4
Mảng lazy[] lưu giá trị cần propagate. Trước mỗi query/update, đẩy lazy xuống. Cập nhật lazy thay vì đệ quy sâu.
Lời giải tham khảo
Xem lời giải
python
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self._build(1, 0, self.n - 1, arr)
def _build(self, node, start, end, arr):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
self._build(2 * node, start, mid, arr)
self._build(2 * node + 1, mid + 1, end, arr)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, l, r):
return self._query(1, 0, self.n - 1, l, r)
def _query(self, node, start, end, l, r):
if r < start or end < l: return 0
if l <= start and end <= r: return self.tree[node]
mid = (start + end) // 2
return (self._query(2*node, start, mid, l, r) +
self._query(2*node+1, mid+1, end, l, r))
def update(self, idx, val):
self._update(1, 0, self.n - 1, idx, val)
def _update(self, node, start, end, idx, val):
if start == end: self.tree[node] = val
else:
mid = (start + end) // 2
if idx <= mid: self._update(2*node, start, mid, idx, val)
else: self._update(2*node+1, mid+1, end, idx, val)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]