Mảng cộng dồn và truy vấn tổng đoạn O(1)
Hệ thống giám sát GPU cluster tại AI Empire Academy ghi lại lượng điện năng tiêu thụ (Watt-hour) của từng phút trong ngày thành một mảng số nguyên nums. Người quản trị cần thực hiệ…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: prefix sum concept, class definition.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu sâu kỹ thuật Mảng cộng dồn (Prefix Sum): Tiền xử lý O(N) để trả lời mọi truy vấn tổng đoạn trong O(1).
- Đóng gói logic vào một lớp (Class) hướng đối tượng.
- Kiểm tra hợp lệ các chỉ số truy vấn
left,right.
Mô tả bài toán
Hệ thống giám sát GPU cluster tại AI Empire Academy ghi lại lượng điện năng tiêu thụ (Watt-hour) của từng phút trong ngày thành một mảng số nguyên nums. Người quản trị cần thực hiện hàng ngàn truy vấn: *"Tính tổng điện năng tiêu thụ từ phút left đến phút right"*.
Nếu mỗi lần truy vấn ta lại dùng vòng lặp cộng từ left đến right, mỗi truy vấn tốn O(K) thời gian. Với Q = 105 truy vấn, hệ thống sẽ bị quá tải.
Hãy xây dựng lớp PrefixSumArray:
__init__(self, nums: list[int]): Khởi tạo và xây dựng mảng cộng dồn tiền xử lý trong O(N) thời gian.range_sum(self, left: int, right: int) -> int: Trả về tổng các phần tử từ chỉ sốleftđếnright(bao gồm cả hai đầu: ∑i=leftright nums[i]) trong thời gian O(1).
Quy tắc bắt lỗi:
- Các chỉ số hợp lệ phải thỏa mãn: 0 ≤ left ≤ right < len(nums).
- Nếu chỉ số không hợp lệ (hoặc mảng ban đầu rỗng), phương thức
range_sumphải ném ra ngoại lệIndexError("Chi so truy van khong hop le").
Input
Lớp được khởi tạo với danh sách nums, sau đó gọi phương thức range_sum(left, right).
Output
Số nguyên int là tổng của đoạn con tương ứng.
Ràng buộc
- Độ dài mảng N: 0 ≤ N ≤ 105.
- -106 ≤ nums[i] ≤ 106.
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
Ví dụ 1
Input
psa = PrefixSumArray([2, -1, 4, 3, -2, 5])
psa.range_sum(1, 3)
psa.range_sum(0, 5)
psa.range_sum(2, 2)Output
6
11
4Giải thích
psa.range_sum(1, 3): (-1) + 4 + 3 = 6.psa.range_sum(0, 5): 2 + (-1) + 4 + 3 + (-2) + 5 = 11.psa.range_sum(2, 2): 4.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.