Sparse Table: truy vấn min đoạn tĩnh bằng hai khối

Khi hỏi nhiều đoạn nhưng mảng không đổi

Cho một mảng cố định, mỗi câu hỏi cần giá trị nhỏ nhất từ l tới trước r. Quét đoạn mất thời gian theo độ dài; Segment Tree trả O(log n) mỗi câu và có thể cập nhật. Nếu dữ liệu thực sự tĩnh, ta có thể tiền xử lý nhiều khối hơn để trả min chỉ bằng hai lần đọc bảng và một phép min.

Sparse Table đánh đổi O(n log n) tiền xử lý và bộ nhớ để có O(1) cho loại truy vấn phù hợp. Không nên chọn chỉ vì nghe O(1): nếu có ít câu hỏi, mảng lớn hoặc bộ nhớ chặt, một cách khác có thể hợp lý hơn. Điều kiện mảng không đổi phải là một phần của việc đọc đề.

Đoạn trong bài dùng dạng nửa mở [l,r), có độ dài r−l. Đoạn phải không rỗng để min được xác định theo giao tiếp này. Tệp không thiết kế một giá trị trả cho truy vấn rỗng; không gọi minimum(l,l) rồi dựa vào một ô bảng tình cờ có giá trị.

Bảng các độ dài 1,2,4,8…

Đặt st[k][i] là min của đoạn [i,i+2^k). Hàng k=0 có độ dài 1, chính là a[i]. Để xây đoạn dài 2^k, chia thành hai nửa dài 2^(k−1): nửa trái bắt đầu i, nửa phải bắt đầu i+2^(k−1). Lấy min hai ô hàng trước.

Chỉ xây những ô mà đoạn không vượt n. Ví dụ với n=6, hàng độ dài 4 chỉ có ba điểm bắt đầu 0,1,2. Những vị trí còn lại không đại diện một đoạn hợp lệ, nên không được đọc chúng khi truy vấn.

Chẳng hạn min đoạn dài 4 bắt đầu 1 là min của đoạn [1,3) và [3,5), lần lượt 2 và 1, nên bằng 1. Tiền xử lý đi hàng k tăng để hai nửa đã có sẵn.

Vì sao hai khối đủ phủ mọi độ dài?

Cho len=r−l và k=floor(log2(len)). Độ dài block=2^k không vượt len, nhưng 2·block lớn hơn hoặc bằng len. Lấy khối đầu [l,l+block) và khối cuối [r−block,r), chúng nằm trong truy vấn và phủ hết khoảng giữa, có thể chồng nhau.

Với len=5, block=4 nên hai khối giao ba phần tử. Với len=4, hai khối có thể trùng hẳn. Với len=1, cả hai cùng là một phần tử. Trong cả ba trường hợp, min vẫn đúng vì gặp lại một giá trị không làm kết quả nhỏ hơn hoặc lớn hơn chính nó.

Công thức trả min(st[k][l],st[k][r−block]). Tọa độ khối phải là r−block vì r không thuộc đoạn. Viết r−block+1 theo công thức đoạn đóng rồi dùng trong đoạn nửa mở sẽ lệch một vị trí.

Chạy tay ba truy vấn

Hai truy vấn cuối là đầu ra mặc định của chương trình. Truy vấn đầu minh họa trong hình để quan sát phần giao rõ hơn. Không cần chia đoạn thành những khối hoàn toàn rời nhau để hỏi min, chính tính chất cho phép lặp đã giúp giảm số khối xuống hai.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class SparseTable{
    vector<int> lg;vector<vector<long long>> table;
public:
    explicit SparseTable(const vector<long long>& a){
        int n=a.size();lg.assign(n+1,0);
        for(int i=2;i<=n;++i)lg[i]=lg[i/2]+1;
        table.assign(lg[n]+1,vector<long long>(n));table[0]=a;
        for(int j=1;j<(int)table.size();++j)
            for(int i=0;i+(1<<j)<=n;++i)table[j][i]=min(table[j-1][i],table[j-1][i+(1<<(j-1))]);
    }
    long long minimum(int l,int r)const{
        int j=lg[r-l];return min(table[j][l],table[j][r-(1<<j)]);
    }
};
int main(){
    int n,q;
    if(cin>>n>>q){
        vector<long long>a(n);for(auto& x:a)cin>>x;SparseTable t(a);
        for(int z=0,l,r;z<q;++z){cin>>l>>r;cout<<t.minimum(l,r)<<'\n';}
    }else{SparseTable t({7,2,6,3,1,5});cout<<t.minimum(1,5)<<'\n'<<t.minimum(0,3)<<'\n';}
}

import sys

class SparseTable:
    def __init__(self,a):
        n=len(a);self.lg=[0]*(n+1)
        for i in range(2,n+1):
            self.lg[i]=self.lg[i//2]+1
        self.table=[a[:]]
        for j in range(1,self.lg[n]+1):
            size=1<<j;half=size//2;previous=self.table[-1]
            self.table.append([min(previous[i],previous[i+half]) for i in range(n-size+1)])

    def minimum(self,left,right):
        j=self.lg[right-left]
        return min(self.table[j][left],self.table[j][right-(1<<j)])

if __name__=='__main__':
    lines=sys.stdin.read().splitlines()
    if lines:
        n,q=map(int,lines[0].split());t=SparseTable(list(map(int,lines[1].split())))
        for line in lines[2:2+q]:
            l,r=map(int,line.split());print(t.minimum(l,r))
    else:
        t=SparseTable([7,2,6,3,1,5]);print(t.minimum(1,5));print(t.minimum(0,3))

Không nhập dữ liệu, chương trình in 1 rồi 2. Input riêng có n,q, một dòng n giá trị và q dòng l r, mỗi dòng hỏi [l,r). Điều kiện n dương và 0<=l<r<=n. Giá trị C++ cần vừa long long; không có cập nhật sau khi dựng bảng.

Code tiền xử lý thêm lg[len]=floor(log2(len)) cho các độ dài 1 tới n. Nhờ đọc lg và hai ô bảng, truy vấn không phải gọi hàm log số thực rồi làm tròn, tránh phụ thuộc sai số gần biên lũy thừa hai. Hàng n=1 vẫn có k=0 và xử lý đúng một phần tử.

C++ cấp phát mỗi hàng đủ n vị trí rồi chỉ điền ô hợp lệ. Python tạo hàng có đúng số điểm bắt đầu hợp lệ ở độ dài đó. Hai cách dùng bộ nhớ hơi khác, nhưng mọi truy vấn hợp lệ đều chỉ đọc các ô đã được xây.

Tính lặp không đổi: vì sao min được, tổng không được?

Phép min có min(x,x)=x. Vì thế nếu một phần tử thuộc phần giao của hai khối bị xét hai lần, kết quả vẫn như một lần. Max, gcd, AND hoặc OR bit cũng có tính chất lặp không đổi phù hợp trong những bài cấu trúc tương ứng.

Tổng thì khác. Với [7,2,6], hai khối dài 2 có tổng 9 và 8. Cộng lại thành 17, trong khi tổng thật là 15 vì số 2 ở giữa đã bị tính hai lần. Không thay min thành dấu cộng trong truy vấn O(1) rồi coi bảng vẫn giải đúng tổng.

Sparse Table cho tổng có thể ghép các khối rời nhau theo biểu diễn nhị phân và cần O(log n) khối trong cách cơ bản. Nhưng nếu mảng tĩnh và chỉ cần tổng, prefix sum vốn trả O(1) với bộ nhớ O(n), nên thường đơn giản hơn. Cấu trúc tốt phụ thuộc phép toán và thao tác cần hỗ trợ.

Một cập nhật làm bảng cũ mất hiệu lực

Nếu thay a[i], nhiều khối ở nhiều điểm bắt đầu chứa i sẽ phải đổi. Bảng này không có một đường tổ tiên duy nhất như Segment Tree để sửa gọn O(log n). Sửa riêng st[0][i] mà không dựng lại các khối trên chỉ làm một phần bảng mới, một phần cũ.

Code cũng không giữ liên kết tự cập nhật khi bạn đổi mảng gốc bên ngoài: Python sao chép hàng đầu, C++ cũng lưu dữ liệu của bảng riêng. Nếu đề có cập nhật xen kẽ, hãy chuyển sang cấu trúc phù hợp hoặc có kế hoạch dựng lại đã phân tích tổng chi phí.

Từ “tĩnh” không phải chỉ ban đầu dữ liệu được nhập một lần. Nó nghĩa là những giá trị mà mọi truy vấn dùng không thay đổi trong suốt giai đoạn hỏi. Một đề có cả cập nhật và truy vấn nhưng gom offline theo cách riêng có thể khai thác thêm tính chất, nhưng không được áp nguyên lời giải mảng tĩnh mà bỏ các cập nhật.

Độ phức tạp và chọn cấu trúc

Có O(log n) độ dài và tối đa n điểm bắt đầu mỗi hàng, nên tiền xử lý O(n log n), bộ nhớ O(n log n). Mỗi câu hỏi min đọc hằng số ô, nên O(1). Mảng lg cần O(n) thời gian và bộ nhớ bổ sung, không đổi cận tổng.

Không phải trả O(1) thì chương trình luôn nhanh hơn một cấu trúc khác. Tiền xử lý, dung lượng bảng, số lượng truy vấn và cách truy cập bộ nhớ đều ảnh hưởng. Bài này phân tích số thao tác, không đưa tỉ lệ nhanh hơn hoặc số mili giây khi chưa đo.

Mở rộng để trả vị trí min

Nếu cần chỉ số của phần tử nhỏ nhất thay vì giá trị, có thể lưu chỉ số hoặc cặp (giá trị,chỉ số). Phép gộp phải có quy tắc phá hòa, chẳng hạn chỉ số nhỏ hơn nếu giá trị bằng nhau. Lúc đó truy vấn hai khối vẫn chọn theo cùng quy tắc nhất quán.

Không lấy giá trị min rồi quét cả đoạn để tìm vị trí nếu bạn vẫn muốn truy vấn O(1). Cũng không dùng một quy tắc ở tiền xử lý và một quy tắc khác lúc trả kết quả, vì phần giao và giá trị trùng có thể làm vị trí không ổn định.

Kiểm mọi đoạn trên mảng nhỏ

Khi tự kiểm tra trên mảng nhỏ, bạn hãy duyệt mọi cặp đoạn [l, r) không rỗng, lấy giá trị nhỏ nhất bằng vòng lặp quét trực tiếp rồi đối chiếu với truy vấn O(1) của Sparse Table. Hãy chú ý thử n = 1, các độ dài sát lũy thừa của 2 như 7, 8, 9, 16, 17, mảng có số âm và nhiều phần tử trùng nhau.

Tự thử đoạn dài 1, đúng lũy thừa hai, hơn một đơn vị và kết thúc đúng n. Các ca này lần lượt kiểm hàng 0, trường hợp hai khối trùng nhau, phần giao và tọa độ khối cuối. Không thêm đoạn rỗng vào test rồi coi một đầu ra tình cờ là hợp lệ, vì giao tiếp đã yêu cầu l<r.

Luyện ngay trên Big-O Coding

Bài min đoạn trên mảng không đổi khớp trực tiếp Sparse Table. Tự bổ sung ba ca: một phần tử âm, nhiều giá trị min bằng nhau và độ dài truy vấn nằm sát một lũy thừa hai. Sau đó thử biến thể trả vị trí min đầu tiên để luyện thiết kế phép gộp và quy tắc phá hòa.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Sparse Table
• CSES: Static Range Minimum Queries
• C++ reference: min