Cấu trúc dữ liệu & Giải thuật

Thực hành tổng tiền tố để trả lời truy vấn đoạn

Tiền xử lý một lần để tính tổng đoạn bằng hai mốc chỉ số.

Thực hànhThực hành4 phút đọcPython

Mảng 4 · 1 · 7 · 2 · 6. Tổng 1 + 7 + 2 = 14 − 4 = 10. Mở hình lớn ↗

1. Đề bài

Cho dãy số 4, 1, 7, 2, 6. Tính tổng nhiều đoạn [l,r), với chỉ số bắt đầu từ 0. Mỗi truy vấn phải chạy trong O(1) sau khi chuẩn bị dữ liệu.

2. Lập bảng bằng tay

Đặt P[0] bằng 0. P[i] là tổng i phần tử đầu. Dãy P là 0, 4, 5, 12, 14, 20. Tổng [1,4) bằng P[4] trừ P[1], tức 10. Dùng cận phải loại trừ để đoạn rỗng tự cho kết quả 0.

3. Đối chiếu lời giải

Mã dùng một lượt duyệt tạo bảng và kiểm tra đoạn giữa, cả dãy và đoạn rỗng. Nếu kết quả lệch một phần tử, hãy viết rõ r nằm trong hay ngoài đoạn trước khi sửa chỉ số.

Chạy ví dụ bằng python hoc_gt_tong_tien_to.py.

Môi trường thực hành. Python 3.10 trở lên. Ví dụ dùng thư viện chuẩn Python.

Python · hoc_gt_tong_tien_to.pyTải mã nguồn

def tien_to(day):
    p = [0]
    for so in day:
        p.append(p[-1] + so)
    return p

def tong_doan(p, l, r):
    if not 0 <= l <= r < len(p):
        raise IndexError("Đoạn ngoài phạm vi")
    return p[r] - p[l]

p = tien_to([4, 1, 7, 2, 6])
assert tong_doan(p, 1, 4) == 10
assert tong_doan(p, 0, 5) == 20
assert tong_doan(p, 2, 2) == 0
print(p)

4. Bài tập mở rộng

Thử với phần tử âm và truy vấn sát biên. Giải thích điều gì xảy ra khi thay phần tử thứ nhất sau khi đã tạo bảng. Liệt kê những mốc P cần cập nhật lại.

Đọc thêm Tài liệu giải thuật của Princeton.