Bảng thưa cho truy vấn min trên dữ liệu bất biến

Bảng thưa (sparse table) trả lời truy vấn giá trị nhỏ nhất trên dữ liệu bất biến bằng cách ghép hai khối có độ dài là lũy thừa của hai đã tính trước. Các khối được phép chồng nhau vì xét lại một giá trị không đổi kết quả min. Với sinh viên đang chọn giữa tổng tiền tố, cây đoạn và bảng thưa, quy tắc chồng lặp giải thích vì sao cùng công thức truy vấn hằng số lại không dùng được cho tổng.

Dùng dãy [5, 2, 7, 1, 3, 6, 0, 4] và truy vấn đoạn nửa mở [1, 6). Đoạn có năm giá trị: hai, bảy, một, ba và sáu. Lũy thừa lớn nhất của hai không vượt quá năm là bốn. Chọn một khối bốn phần tử bắt đầu tại một và một khối bốn phần tử kết thúc tại sáu. Chỉ số mảng, lũy thừa nguyên của hai và phép lấy min là đủ để theo dõi cách dựng.

Tính trước các khoảng có độ dài gấp đôi

Mức không của bảng lưu từng giá trị riêng. Mức một lưu min trên độ dài hai, mức hai trên độ dài bốn, và tiếp tục như vậy. Khoảng dài 2^k tách thành hai khoảng kề nhau dài 2^(k - 1), nên mỗi ô ghép hai ô của mức trước.

class SparseMin:
    def __init__(self, values):
        values = list(values)
        self.n = len(values)
        self.table = [values]
        width = 2
        while width <= self.n:
            half = width // 2
            previous = self.table[-1]
            row = [min(previous[i], previous[i + half])
                   for i in range(self.n - width + 1)]
            self.table.append(row)
            width *= 2

    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('expected a nonempty half-open interval')
        length = right - left
        level = length.bit_length() - 1
        width = 1 << level
        return min(self.table[level][left], self.table[level][right - width])

values = [5, 2, 7, 1, 3, 6, 0, 4]
ranges = SparseMin(values)
assert ranges.table[2] == [1, 1, 1, 0, 0]
assert ranges.query(1, 6) == 1
assert ranges.query(6, 7) == 0
assert ranges.query(0, 8) == 0

Các hàng ngắn dần vì một khoảng phải nằm trọn trong đầu vào. Với độ dài bốn, tám phần tử cho phép năm vị trí bắt đầu. Truy vấn chọn mức bằng số bit của độ dài đoạn dương, tránh sai số logarithm dấu phẩy động gần các lũy thừa của hai.

Lớp từ chối đoạn rỗng. Min của đoạn rỗng không có giá trị thành viên thông thường, nên giao diện báo khoảng không hợp lệ thay vì đưa vào một giá trị vô cùng làm dấu. Có thể dựng từ đầu vào rỗng, nhưng khi đó không có truy vấn không rỗng hợp lệ.

Mở ảnh kích thước đầy đủ ↗

Trong ví dụ, khối [1, 5) chứa 2, 7, 1, 3, còn khối [2, 6) chứa 7, 1, 3, 6. Cả hai đều có min bằng một. Hợp của chúng chính xác là đoạn cần hỏi, dù ba giá trị ở giữa xuất hiện trong cả hai khối.

Chồng lặp an toàn vì min có tính lũy đẳng

Gọi độ dài truy vấn là L, độ rộng khối đã chọn là w, với w <= L < 2w. Khối đầu phủ w vị trí bên trái; khối sau phủ w vị trí bên phải. Vì L < 2w, chúng chồng nhau và không để hở khoảng nào. Khi L = w, hai khối hoàn toàn trùng nhau. Không khối nào vượt khỏi truy vấn.

Min của hai kết quả min vì thế là min trên hợp hai khối. Một giá trị nằm trong phần chồng bị xét hai lần, nhưng min(x, x) = x. Đây là tính lũy đẳng (idempotence), điều kiện bổ sung cho phép dùng các kết quả có phần chồng trong cách truy vấn này.

Chỉ tính kết hợp cho phép đổi cách nhóm các đoạn rời nhau, chưa đủ để biện minh cho việc đếm một đoạn hai lần. Phần giải thích bảng thưa của CP-Algorithms phân biệt truy vấn min hằng số với những phép toán không dùng được lối tắt chồng lặp ấy.

Áp dụng cùng hai khối cho tổng để thấy lỗi

Tổng của [1, 5) là mười ba, còn tổng của [2, 6) là mười bảy. Cộng lại được ba mươi. Đoạn thật [1, 6) chỉ có tổng mười chín. Chênh lệch mười một chính là phần chồng bị lặp: 7 + 1 + 3.

Kết quả min đúng không nhờ một mẹo chỉnh chỉ số bên trong min. Đặc tính của phép tổng hợp khiến lặp dữ liệu trở nên vô hại. Thay min bằng cộng trong truy vấn hai khối làm thay đổi đặc tính ấy và phá vỡ chứng minh.

Bảng thưa thông thường vẫn có thể trả lời tổng bằng cách chia đoạn thành những khối lũy thừa của hai không chồng nhau, chọn O(log n) khối. Với tổng trên dữ liệu bất biến, mảng tiền tố thường đơn giản hơn: dựng O(n), truy vấn O(1). Bảng thưa rời nhau (disjoint sparse table) là cấu trúc khác, có cách tiền xử lý và lập luận truy vấn riêng; không nên nhầm với cách dựng chồng khối ở đây.

Chỉ trả chi phí tiền xử lý khi phù hợp

Có O(log n) mức, mỗi mức nhiều nhất n ô, nên thời gian dựng và bộ nhớ là O(n log n). Truy vấn min hợp lệ đọc hai ô và gọi min một lần, cho O(1) công việc trong mô hình chỉ số vừa một từ máy. Chi phí dựng đáng trả khi nhiều truy vấn tái sử dụng cùng dữ liệu.

Thay đổi một phần tử làm nhiều khoảng đã lưu chứa vị trí đó mất hiệu lực. Lớp này không có thao tác cập nhật mà dựng lại bảng khi dữ liệu đổi, tốn O(n log n). Nếu dữ liệu đổi thường xuyên, cây đoạn hỗ trợ cả cập nhật và truy vấn logarithm; giao diện cây đoạn của AtCoder thể hiện rõ sự đánh đổi này.

Bộ nhớ có thể quyết định lựa chọn trước cả tốc độ truy vấn. Một đầu vào vừa trong một mảng chưa chắc còn vừa sau khi lưu nhiều mức tham chiếu hoặc mảng số. Ước lượng cách biểu diễn phần tử và số mức thực tế, rồi so với cây đoạn hoặc cấu trúc min đoạn khác phù hợp tải công việc.

Kiểm tra mọi đoạn không rỗng của một dãy ngắn bằng min trực tiếp. Bao gồm độ dài đúng lũy thừa của hai và lớn hơn lũy thừa một đơn vị, nơi cách chồng thay đổi. Các giá trị min lặp lại và một giá trị nhỏ nhất nằm ngay ngoài đoạn giúp phát hiện việc phủ quá biên. Cài đặt thu một đối tượng lặp hữu hạn đúng một lần và sao chép tham chiếu, nên việc bên gọi thay ô trong danh sách không cập nhật bảng. Bản thân các giá trị được tham chiếu phải bất biến và có thứ tự toàn phần; sao chép nông danh sách không đóng băng đối tượng khả biến. Loại trừ NaN dấu phẩy động vì phép so sánh của nó không cung cấp thứ tự mà chứng minh min cần.

Trả vị trí của min với quy tắc hòa ổn định

Biểu đồ có thể cần đánh dấu mẫu thấp nhất xuất hiện sớm nhất, thay vì chỉ in giá trị. Lưu mỗi mẫu kèm vị trí gốc thành (value, index). Python so sánh tuple theo thứ tự từ điển: trước hết chọn giá trị nhỏ nhất, rồi chỉ số nhỏ nhất. min trên các cặp vẫn có tính kết hợp và lũy đẳng. Chứng minh truy vấn chồng khối vẫn áp dụng, kể cả khi cùng một cặp xuất hiện trong cả hai khối.

samples = [4, 1, 1, 5, 1]
positions = SparseMin((value, index)
                      for index, value in enumerate(samples))
assert positions.query(1, 5) == (1, 1)
assert positions.query(2, 5) == (1, 2)
assert positions.query(3, 4) == (5, 3)
samples[1] = 9
assert positions.query(1, 5) == (1, 1)
rebuilt = SparseMin((value, index)
                    for index, value in enumerate(samples))
assert rebuilt.query(1, 5) == (1, 2)

Trong [1, 5), các vị trí một, hai và bốn đều chứa một, và cặp có vị trí đầu tiên thắng. Dời biên trái sang hai loại ứng viên sớm hơn mà không đổi quy tắc. Thay samples[1] sau đó không sửa bảng hiện có: các tuple giá trị-chỉ số đã được thu lại. Dựng lại sẽ chọn vị trí hai theo đầu vào mới. Sự khác biệt này quan trọng khi người dùng sửa dữ liệu biểu đồ nhưng ứng dụng vẫn giữ cấu trúc truy vấn cũ.

Mở ảnh kích thước đầy đủ ↗

Quy tắc hòa phải nằm trong phép tổng hợp, không phụ thuộc khối nào tình cờ được hỏi trước. Muốn chọn vị trí muộn nhất, so sánh (value, -index) rồi đổi dấu trường thứ hai để lấy chỉ số gốc. Công bố lựa chọn trong giao diện: hai quy tắc trả cùng giá trị min nhưng có thể đánh dấu các mẫu khác nhau. So sánh tuple ở đây xét tối đa hai trường, với cùng giả định chi phí so sánh giá trị hằng số như bản chỉ dùng số.

Kích thước bảng chính xác giúp thấy rõ đánh đổi bộ nhớ. Với tám giá trị, độ dài các hàng hợp lệ là tám, bảy, năm và một, tổng cộng hai mươi mốt ô. Một thay đổi giả định tại vị trí ba ảnh hưởng một đoạn đơn, hai đoạn dài hai, bốn đoạn dài bốn và đoạn dài tám duy nhất. Có tám đáp án đã lưu có thể cần sửa, trong khi cây đoạn chỉ đổi một tổ tiên mỗi mức. Cơ chế sửa chuyên biệt không nhất thiết dựng lại mọi ô, nhưng lớp tĩnh này chỉ cung cấp việc dựng lại; số mức logarithm không suy ra chi phí cập nhật logarithm.

Để luyện tập, dùng dãy năm mẫu và đối chiếu mọi đoạn với min((samples[i], i) for i in range(left, right)). Lặp lại sau một lần sửa bằng bảng mới, rồi cài quy tắc vị trí muộn nhất. Bao gồm đoạn có mẫu thấp nhất duy nhất nằm ngay ngoài biên trái. Trường hợp đó phân biệt quy tắc hòa hợp lệ với truy vấn bị kéo quá rộng.