Tổng tiền tố cho nhiều truy vấn tổng đoạn
Dùng ranh giới nửa mở để lấy tổng đoạn, kiểm tra giá trị âm và đoạn rỗng, rồi tái hiện sai số khi các tổng lớn làm mất đơn vị nhỏ.
Tổng tiền tố tại một ranh giới lưu tổng các giá trị đứng trước ranh giới đó. Khi có số 0 dẫn đầu, tổng đoạn nửa mở [left, right) luôn là prefix[right] - prefix[left]. Với sinh viên cần trả lời nhiều truy vấn đoạn, quy ước này loại bỏ trường hợp riêng cho đoạn bắt đầu ở chỉ số 0 và cho đoạn rỗng kết quả tự nhiên là 0.
Xét các giá trị [4, -1, 3, 0, 2]. Mảng tiền tố là [0, 4, 3, 6, 6, 8]. Vị trí ba lưu tổng các giá trị ở chỉ số không, một và hai. Mảng tiền tố dài hơn đầu vào một phần tử vì nó mô tả mọi ranh giới, kể cả ranh giới sau giá trị cuối.
Trừ đi phần đầu được dùng chung
Đoạn từ chỉ số một tới chỉ số ba, tính cả hai đầu, được viết thành [1, 4). Tổng trước ranh giới bốn là sáu; tổng trước ranh giới một là bốn. Lấy hiệu được hai, đúng bằng -1 + 3 + 0.
def prefix_sums(values):
prefix = [0]
for value in values:
prefix.append(prefix[-1] + value)
return prefix
def range_sum(prefix, left, right):
if type(left) is not int or type(right) is not int or not 0 <= left <= right < len(prefix):
raise IndexError('expected 0 <= left <= right <= n')
return prefix[right] - prefix[left]
prefix = prefix_sums([4, -1, 3, 0, 2])
assert prefix == [0, 4, 3, 6, 6, 8]
assert range_sum(prefix, 1, 4) == 2
assert range_sum(prefix, 2, 2) == 0
assert range_sum(prefix, 0, 5) == 8
assert range_sum(prefix_sums([]), 0, 0) == 0Kiểm tra cận cho phép right == n vì mảng tiền tố có độ dài n + 1. Nó từ chối đoạn đảo đầu cuối, chỉ số âm và đầu mút vượt nguồn. Nếu không kiểm tra, chỉ số âm của Python sẽ âm thầm đọc từ cuối mảng tiền tố rồi tạo một đáp án có vẻ hợp lý nhưng sai.
Hình đánh nhãn ranh giới riêng với vị trí phần tử. Một mục tiền tố thuộc về trước hoặc sau một đoạn giá trị; nhầm nó với phần tử mang cùng chỉ số số học là nguyên nhân thường gặp của lỗi lệch một vị trí.
Suy ra công thức từ phép triệt tiêu
Theo định nghĩa, prefix[right] chứa mọi giá trị trước right. Có thể chia chúng thành nhóm trước left và nhóm nằm trong [left, right). Tổng nhóm đầu là prefix[left], nên trừ nó sẽ để lại đúng đoạn cần hỏi.
Lập luận vẫn đúng khi left == right: hai tiền tố mô tả cùng tập giá trị và triệt tiêu thành 0. Nó cũng đúng với đoạn toàn mảng bắt đầu tại 0 vì tiền tố dẫn đầu bằng 0. Cả hai trường hợp đều không cần nhánh điều kiện riêng.
Giá trị âm không làm công thức mất hiệu lực. Chúng có thể khiến tổng phía sau nhỏ hơn tổng phía trước, như tổng giảm từ bốn xuống ba khi đọc âm một. Phần tổng tiền tố của USACO Guide phát triển cách tiền xử lý và lấy hiệu cho truy vấn đoạn.
Muốn các tổng tiền tố không giảm, cần đầu vào không âm. Nếu thuật toán khác dùng tìm kiếm nhị phân để tìm tiền tố đầu tiên vượt ngưỡng, nó cần giả định bổ sung ấy hoặc một chứng minh đơn điệu khác. Chỉ tính đúng tổng đoạn chưa thiết lập tính đơn điệu.
Tiền xử lý có ích khi có nhiều truy vấn
Xây mảng tiền tố cần Θ(n) phép cộng và Θ(n) bộ nhớ. Mỗi truy vấn đã kiểm tra cận sau đó dùng truy cập chỉ số hằng số cùng một phép trừ. Với q truy vấn trên dữ liệu không đổi, tổng công việc là Θ(n + q), thay cho mức tới Θ(nq) nếu mỗi truy vấn quét đoạn của mình.
Cận này giả sử cộng và trừ có chi phí hằng số trong biểu diễn số đã chọn. Python biểu diễn được số nguyên lớn tùy ý, nhưng phép toán đắt hơn khi độ dài bit tăng. Cài đặt số nguyên độ rộng cố định cần bộ tích lũy đủ rộng cho tổng lớn nhất hoặc chính sách tràn số rõ ràng.
Số thực dấu phẩy động có giới hạn khác. Lấy hiệu tiền tố có thể mất độ chính xác khi trừ hai tổng lớn gần bằng nhau để thu một đoạn nhỏ. Nếu sai số quan trọng, cần chọn cách cộng và lưu dựa trên miền giá trị cùng độ chính xác yêu cầu. Đồng nhất thức đại số đúng trong số học chính xác; tính toán hữu hạn chỉ xấp xỉ nó.
Nếu chỉ hỏi một đoạn ngắn, tính mọi tiền tố có thể làm nhiều việc hơn quét trực tiếp đoạn đó. Tổng tiền tố là lựa chọn tối ưu theo tải, nên cần xét số truy vấn dự kiến và độ dài đoạn trước khi thêm một mảng nữa.
Cập nhật làm thay đổi một hậu tố của mảng tiền tố
Đổi giá trị tại chỉ số i ảnh hưởng mọi ranh giới tiền tố sau i. Cập nhật mảng tiền tố đã tính vì vậy có thể cần Θ(n) lần ghi. Nếu dữ liệu thường xuyên đổi giữa các truy vấn, xây lại liên tục có thể làm mất lợi ích của truy vấn tổng hằng số.
Cây Fenwick hoặc cây đoạn dùng biểu diễn phức tạp hơn để đổi lấy cập nhật và truy vấn logarithm. Phần truy vấn tổng của cây Fenwick giải thích cách lưu một số tổng thành phần để tránh chạm toàn bộ hậu tố sau một thay đổi. Mảng tiền tố tĩnh vẫn đơn giản hơn khi dữ liệu bất biến hoặc các cập nhật đến thành lô lớn giữa những giai đoạn truy vấn.
Phương pháp lấy hiệu còn phụ thuộc vào khả năng triệt tiêu của phép tổng hợp. Không thể lấy hiệu hai giá trị nhỏ nhất tiền tố để tìm giá trị nhỏ nhất trên một đoạn bất kỳ. Một giá trị nhỏ trước đoạn hỏi có thể chi phối cả hai tiền tố mà không cho biết cực tiểu bên trong đoạn. Chỉ có tính kết hợp chưa đủ để suy ra công thức hiệu tiền tố.
Kiểm tra đoạn bằng các ranh giới
Với mảng nhỏ, liệt kê mọi cặp 0 <= left <= right <= n và so kết quả tiền tố với tổng trực tiếp của lát cắt. Gồm số âm, số 0, mảng rỗng và đoạn chạm hai đầu. Phép kiểm tra ấy xét quy ước ranh giới trên mọi đoạn nhỏ thay vì chỉ vài ví dụ thuận tiện.
Nếu API bên ngoài dùng hai đầu mút đều được tính, chuyển [left, last] thành [left, last + 1) tại ranh giới API và kiểm tra tính hợp lệ hoặc tràn số ở đó. Giữ quy ước của hàm bên trong nhất quán. Trộn đầu mút đóng và mở trong cùng công thức khó duyệt hơn một phép chuyển có chủ ý tại bên gọi.
Tái hiện một đoạn nhỏ bị mất sau tổng lớn
Giới hạn số thực xuất hiện ngay trong dữ liệu rất nhỏ. Đặt giá trị 10**16 trước hai giá trị đơn vị. Ở độ lớn ấy, biểu diễn binary64 không chứa được mọi số nguyên, nên cộng một có thể làm tròn về đúng tổng cũ. Cả hai lần cộng đều có thể biến mất trong lượt quét tiền tố dù đoạn được hỏi chứa hai giá trị đơn vị chính xác.
import math
floating = [1e16, 1.0, 1.0]
floating_prefix = prefix_sums(floating)
assert floating_prefix == [0, 1e16, 1e16, 1e16]
assert range_sum(floating_prefix, 1, 3) == 0.0
assert math.fsum(floating[1:3]) == 2.0
exact = [10**16, 1, 1]
assert range_sum(prefix_sums(exact), 1, 3) == 2
careful_prefix = [math.fsum(floating[:end]) for end in range(4)]
assert careful_prefix[2] - careful_prefix[1] == 0.0Mảng hữu hạn và mọi giá trị đều không âm. Lỗi không đến từ số âm hoặc đoạn sai cận. Chứng minh triệt tiêu chính xác giả sử các tiền tố lưu trữ bằng tổng toán học của chúng. Ở đây việc làm tròn trước đó đã loại thông tin trước cả khi thực hiện phép trừ.
math.fsum của Python theo dõi nhiều tổng thành phần để giảm sai số tích lũy. Nó giúp khi cộng trực tiếp đoạn ngắn, nhưng dùng riêng nó cho từng tiền tố không khiến mọi ranh giới biểu diễn chính xác bằng một số thực. Tổng toán học 10**16 + 1 vẫn phải làm tròn khi lưu thành binary64, nên phép xác nhận cuối không khôi phục được đơn vị giữa ranh giới một và hai.
Cách dựng careful_prefix ở đây chỉ là phép khảo sát nhỏ, không phải thuật toán tiền xử lý được đề xuất. Nó cộng lại các lát cắt nhiều lần nên tổng công việc đọc đầu vào là bậc hai, kèm cấp phát các lát cắt. Mục đích là tách việc cộng cẩn thận hơn khỏi độ chính xác của từng kết quả lưu. Duy trì bộ tích lũy có bù sai số trong một lượt có cài đặt và chi phí khác, nhưng lưu chỉ một số đã làm tròn tại mỗi ranh giới vẫn cần phân tích độ chính xác.
Lưu số nguyên phù hợp khi miền dữ liệu thực sự gồm đơn vị rời rạc, chẳng hạn số sự kiện. Số nguyên lớn của Python giữ tổng chính xác trong ví dụ, với điều kiện về chi phí bit đã nêu. Nhân một số thực tùy ý với hệ số rồi đổi sang số nguyên không tự động chính xác: ứng dụng phải xác định đơn vị và quy tắc chuyển đổi trước khi dựng mảng. Số thập phân hoặc phân số cũng có hợp đồng riêng về biểu diễn, độ chính xác và hiệu năng.
Để luyện tập về số học, chuyển giá trị lớn xuống cuối rồi so cùng đoạn nhỏ ở đầu. Sau đó đổi độ lớn và ghi nhận điểm đầu tiên một lần tăng đơn vị bị mất trong biểu diễn số thực đã chọn. So với tham chiếu số nguyên chính xác thay vì một cài đặt khác lặp lại cùng phép toán đã làm tròn. Cách này kiểm tra mô hình số riêng với công thức ranh giới.
Hàm nhận đầu mút là kiểu số nguyên tích hợp và từ chối Boolean cùng chỉ số phân số trước khi truy cập mảng. Nó giả sử mảng tiền tố đã được xây theo mô hình số học dự định; kiểm tra cận không xác thực nội dung hoặc làm tiền tố cũ khớp nguồn vừa thay đổi. Khi đưa cách tối ưu này vào API ứng dụng, hãy giữ cách xây dựng, phiên bản dữ liệu và ý nghĩa truy vấn đi cùng nhau.