phân hủy gốc

Chúng ta gặp vấn đề về cách tính nhanh các tổng trên khoảng l...r trong một mảng tĩnh a với số tiệm cận nhỏ hơn O(n).

Hãy chia mảng a thành k khối có cùng kích thước và trước tiên hãy tính tổng các phần tử của mỗi khối.

Bây giờ, khi trả lời yêu cầu, chúng ta có thể duyệt qua các phần tử của mảng a và thêm chúng vào kết quả, đồng thời nếu một trong các khối nằm bên trong phân đoạn, thì chúng ta có thể cộng tổng của nó vào kết quả và bỏ qua các phần tử của khối này.

Số lượng thao tác tối đa cho mỗi truy vấn với thuật toán này là n / k + k, vì vậy k tối ưu bằng căn bậc hai của n.

 

Chúng ta gặp vấn đề về cách tính nhanh tổng trên đoạn l...r trong mảng a, trong đó các phần tử có thể thay đổi từng phần tử một, theo các tiệm cận nhỏ hơn O(n).

Tác vụ này được giải quyết tương tự như tác vụ trước, nhưng khi yêu cầu thay đổi, bạn cần thay đổi số lượng trong khối tương ứng.

Một nhiệm vụ được đưa ra trong đó cần thực hiện các thao tác hàng loạt trên một phân đoạn và nhận dạng một phần tử theo chỉ mục.

Các hoạt động hàng loạt được thực hiện dưới dạng phép tính tổng trên một phân đoạn.

Đối với mỗi khối, chúng tôi lưu trữ thay đổi trong khối đó và khi yêu cầu một thành phần từ khối đó, chúng tôi sẽ tính đến thông tin đó.