Cây đoạn cho truy vấn tổng và giá trị nhỏ nhất
Dùng tính kết hợp và phần tử trung hòa để ghép đoạn, giữ đúng thứ tự và kiểm tra bằng hợp thành hàm có cập nhật.

Cây đoạn (segment tree) lưu kết quả tổng hợp cho các khoảng và ghép một số ít khoảng đó để trả lời truy vấn. Cùng một cấu trúc có thể tính tổng hoặc lấy giá trị nhỏ nhất nếu phép ghép có tính kết hợp và phần tử trung hòa. Với lập trình viên đang xây truy vấn đoạn có cập nhật, các điều kiện đại số này giải thích cả khả năng tái sử dụng lẫn những lỗi thường gặp.
Để tính tổng, dùng phép cộng với phần tử trung hòa bằng không. Để lấy giá trị nhỏ nhất trong các số hữu hạn, dùng min với dương vô cùng. Ghép bất kỳ giá trị hợp lệ nào với phần tử trung hòa phải giữ nguyên giá trị đó. Nhờ vậy, đoạn rỗng có kết quả xác định và các lá đệm không làm thay đổi truy vấn thật. Ví dụ Python giả định bạn đã biết vòng lặp và chỉ số danh sách bắt đầu từ không; không cần từng cài cây trước đó.
Lưu cây đầy đủ trên các lá có đệm
Làm tròn số lá lên một lũy thừa của hai. Đặt các giá trị gốc tại các lá liên tiếp, rồi điền phần tử trung hòa vào những lá còn lại. Mỗi nút trong ghép kết quả của con trái với con phải theo đúng thứ tự đó. Quá trình dựng từ dưới lên thăm mỗi nút trong một lần.
class SegmentTree:
def __init__(self, values, combine, identity):
values = list(values)
self.n = len(values)
self.combine, self.identity = combine, identity
self.size = 1
while self.size < self.n:
self.size *= 2
self.tree = [identity] * (2 * self.size)
self.tree[self.size:self.size + self.n] = values
for i in range(self.size - 1, 0, -1):
self.tree[i] = combine(self.tree[2 * i], self.tree[2 * i + 1])
def set(self, position, value):
if type(position) is not int or not 0 <= position < self.n:
raise IndexError(position)
i = self.size + position
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.combine(self.tree[2 * i], self.tree[2 * i + 1])
def query(self, left, right):
if (type(left) is not int or type(right) is not int
or not 0 <= left <= right <= self.n):
raise IndexError('invalid half-open range')
left += self.size
right += self.size
before = after = self.identity
while left < right:
if left & 1:
before = self.combine(before, self.tree[left])
left += 1
if right & 1:
right -= 1
after = self.combine(self.tree[right], after)
left //= 2
right //= 2
return self.combine(before, after)
values = [5, 2, 7, 1, 3]
sums = SegmentTree(values, lambda a, b: a + b, 0)
mins = SegmentTree(values, min, float('inf'))
assert sums.query(1, 4) == 10
assert mins.query(1, 4) == 1
sums.set(3, 6)
mins.set(3, 6)
assert sums.query(1, 4) == 15
assert mins.query(1, 4) == 2
Hàm dựng thu toàn bộ một đối tượng lặp hữu hạn thành danh sách đúng một lần, nên chấp nhận bộ sinh mà không cần hỏi độ dài trước. Danh sách bổ sung này lưu O(n) tham chiếu. Đối số chỉ số phải là số nguyên kiểu int của Python; giá trị boolean và vị trí phân số bị từ chối. Vị trí đầu vào và truy vấn bắt đầu từ không, còn đầu phải không thuộc đoạn. Các lá đệm chỉ là chi tiết nội bộ. Kiểm tra biên ngăn bên gọi truy vấn ra ngoài dữ liệu gốc dù cây còn các lá trung hòa.
Với truy vấn ban đầu [1, 4), cây ghép [1, 2) với [2, 4). Tổng của hai đoạn là hai và tám, cho kết quả mười. Giá trị nhỏ nhất của chúng là hai và một, cho kết quả một. Cách chia đoạn giữ nguyên; chỉ phép ghép thay đổi.
Tính kết hợp cho phép đổi cách nhóm, không cho phép đổi thứ tự
Phép toán có tính kết hợp khi combine(combine(a, b), c) = combine(a, combine(b, c)). Vì thế, truy vấn có thể nhóm các giá trị liên tiếp theo những nút của cây mà không đổi đáp án. Không cần tính giao hoán, tức khả năng đổi chỗ a với b.
Nối chuỗi là một ví dụ: đổi cách nhóm vẫn giữ chuỗi, nhưng đảo hai đoạn thì không. Bởi vậy, truy vấn giữ hai kết quả tích lũy riêng ở bên trái và bên phải. Đoạn tìm thấy bên trái được nối sau before; đoạn tìm thấy bên phải được nối trước after. Ghép hai phần cuối cùng sẽ khôi phục thứ tự gốc.
letters = SegmentTree(iter('abcdefgh'), lambda a, b: a + b, '')
assert letters.query(1, 7) == 'bcdefg'
assert letters.query(2, 2) == ''
Với [1, 7), phía phải tìm thấy g trước, rồi mới thấy ef. Nối vào đầu tạo efg; nối vào cuối sẽ tạo sai thành gef. Phần tích lũy bên trái chứa bcd, nên đáp án sai cuối cùng là bcdgef. Truy vấn như [1, 4) không đi qua hai khối ở biên phải này và sẽ bỏ sót lỗi. Các kiểm tra tổng và min cũng không phát hiện được vì hai phép toán đó có tính giao hoán. Tài liệu cây đoạn của AtCoder nêu rõ yêu cầu về tính kết hợp và phần tử trung hòa.
Cập nhật đi lại trên một đường tổ tiên
Đổi một lá chỉ ảnh hưởng các khoảng chứa vị trí ấy. Tính lại nút cha, rồi cha của cha, cho tới gốc. Chiều cao là O(log n), nên phép gán tại một vị trí có chi phí đó. Mỗi mức của truy vấn chỉ chọn một số nút biên bị giới hạn bởi hằng số, nên truy vấn đoạn cũng tốn O(log n).
Các cận này đếm số lần gọi phép ghép và giả định mỗi lần ghép hoặc sao chép kết quả có chi phí O(1). Số lá sau đệm nhỏ hơn hai lần độ dài đầu vào dương, nên cây có O(n) ô lưu kết quả và quá trình dựng gọi phép ghép O(n) lần. Đầu vào rỗng vẫn có vùng lưu trung hòa; chỉ truy vấn đoạn rỗng là hợp lệ. Dương vô cùng trả về cho min của đoạn rỗng là quy ước biểu thị không có thành viên hữu hạn, không phải một giá trị nhỏ nhất đã quan sát.
Hướng dẫn cây đoạn của CP-Algorithms giải thích cách chia khoảng và các mở rộng phổ biến. Cập nhật cả đoạn cần cơ chế bổ sung như truyền cập nhật lười. Gọi set cho từng vị trí trong một đoạn dài không thừa hưởng chi phí logarithm của một lần gán điểm.
Chọn phép tổng hợp có ý nghĩa phù hợp
Phép cộng số thực dấu phẩy động không có tính kết hợp tuyệt đối, nên cách nhóm của cây có thể tạo tổng làm tròn khác với quét từ trái sang phải. Đây là giới hạn số học của phép toán, không phải lỗi chỉ số. Khi cần tổng tiền có khả năng tái lập, biểu diễn thập phân cố định hoặc số nguyên theo đơn vị có thể phù hợp hơn, tùy quy tắc ứng dụng.
Cài đặt còn giả định phép ghép không sửa đối tượng trung hòa hay kết quả của các nút con đang được dùng chung. Dùng danh sách khả biến làm phần tử trung hòa rồi nối tại chỗ sẽ vi phạm giả định đó, vì nhiều ô ban đầu cùng tham chiếu một đối tượng. Hãy dùng kết quả bất biến hoặc tạo các đối tượng riêng với phép ghép được định nghĩa cẩn thận.
Kiểm tra mọi đoạn ngắn sau mỗi lần gán điểm và so với phép tổng hợp trực tiếp. Bao gồm đoạn rỗng, cập nhật vị trí cuối và độ dài không phải lũy thừa của hai. Dùng ít nhất một phép toán không giao hoán như nối chuỗi để kiểm tra thứ tự khoảng. Điều kiện đại số giúp mã dùng chung được; kiểm tra cần bao phủ điều kiện ấy thay vì chỉ một phép số học thuận tiện.
Hợp thành phép biến đổi mà không sao chép chuỗi
Nối chuỗi hữu ích để thử thứ tự, nhưng chi phí sao chép khiến nó không phải phép tổng hợp hằng số. Với một ký tự tại mỗi lá, tổng độ dài các chuỗi trên mỗi mức có thể là O(n), dẫn tới O(n log n) ký tự được lưu. Trả một chuỗi dài cũng tốn thời gian theo độ dài ấy. Số lần ghép logarithm không xóa được phần công việc này.
Một kết quả có kích thước gọn là hàm affine f(x) = a*x + b, lưu bằng cặp (a, b). Đọc khoảng từ trái sang phải: áp dụng phép biến đổi đầu, rồi phép thứ hai. Ghép (a, b) với (c, d) vì thế cho (c*a, c*b + d). Hợp thành hàm có tính kết hợp nhưng thường không giao hoán. Phần tử trung hòa là (1, 0).
def then(first, second):
a, b = first
c, d = second
return c * a, c * b + d
transforms = [(2, 0), (1, 3), (-1, 0), (1, 4)]
functions = SegmentTree(iter(transforms), then, (1, 0))
assert functions.query(1, 4) == (-1, 1)
a, b = functions.query(1, 4)
assert a * 5 + b == -4
assert functions.query(0, 0) == (1, 0)
functions.set(2, (1, 0))
assert functions.query(1, 4) == (1, 7)
Khoảng ban đầu cộng ba, đổi dấu kết quả, rồi cộng bốn. Bắt đầu từ năm sẽ lần lượt được tám, âm tám và âm bốn. Đảo thứ tự thao tác lại cho âm sáu, nên chỉ có đúng tập thao tác vẫn chưa đủ. Sau khi thay phép đổi dấu bằng hàm đồng nhất, cả khoảng chỉ cộng bảy. Ví dụ kiểm tra cả hướng hợp thành và phép gán điểm bằng những cặp số bất biến.
Hệ số nguyên Python có thể lớn dần khi hợp thành, nên chi phí theo số bit vẫn đáng tính dù số trường dữ liệu không đổi. AtCoder nêu rõ độ phức tạp phụ thuộc chi phí phép toán. Cũng cần phép ghép thuần, được định nghĩa cho mọi kết quả có thể xuất hiện: cài đặt nhỏ này không hoàn tác một lần gán nếu mã ghép do bên gọi cung cấp phát sinh ngoại lệ giữa lúc tính lại tổ tiên.
Để luyện tập, thay thao tác cuối “cộng bốn” bằng “nhân đôi”, tự tính hệ số của khoảng rồi đối chiếu mọi đoạn không rỗng với việc áp dụng trực tiếp lên vài số nguyên. Sau đó cố ý đổi tích lũy bên phải thành nối vào cuối và tìm đoạn ngắn nhất bị sai trong dãy tám chữ cái. Hai phép thử tách hướng đại số khỏi sự trùng hợp về số.