Căn bậc hai mảng (Sqrt Decomposition) và Truy vấn tổng khoảng

Mục tiêu kiến thức

• Hiểu nguyên lý chia khối căn bậc hai (Sqrt Decomposition) với kích thước khối B = lceil √(N) rceil.
• Truy vấn tổng đoạn [L, R] trong thời gian O(√(N)).
• Cập nhật giá trị tại 1 điểm trong thời gian hằng số O(1).

Mô tả bài toán

Viết lớp SqrtDecomposition:

• __init__(self, nums: list[int]): Khởi tạo và tiền tính toán tổng của từng khối. Kích thước khối B = max(1, int(N^0.5)). Nếu nums rỗng, raise ValueError("Mang khong duoc rong").
• query_sum(self, left: int, right: int) -> int: Tính tổng các phần tử trong đoạn [left, right] (0-indexed).
• Duyệt tuần tự các phần tử lẻ ở đầu và đuôi, cộng dồn trực tiếp tổng các khối nguyên nằm trọn vẹn ở giữa.
• Nếu left > right hoặc left < 0 hoặc right ≥ len(nums), raise IndexError("Khoang truy van ngoai pham vi").
• update(self, index: int, value: int) -> None: Cập nhật nums[index] = value, đồng thời cập nhật lại tổng của khối chứa index trong O(1).
• Nếu index < 0 hoặc index >= len(nums), raise IndexError("Chi so ngoai pham vi").

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.