Chia khối và lưu các giá trị đã sắp xếp

Chia dãy thành các khối dài khoảng \(B\). Mỗi khối lưu thêm một bản sao các giá trị đã sắp xếp. Dãy ban đầu vẫn giữ thứ tự theo vị trí.

Với thao tác đếm trên \([a,b]\):

• Duyệt từng phần tử ở tối đa hai khối bị cắt tại hai biên.
• Với mỗi khối nằm trọn trong đoạn, dùng tìm kiếm nhị phân để tìm vị trí đầu tiên có giá trị lớn hơn hoặc bằng \(c\). Số phần tử từ đó tới cuối khối là phần đóng góp.

Nếu hai đầu thuộc cùng một khối, chỉ duyệt đoạn đó một lần.

Với thao tác gán tại vị trí \(a\), tìm và xóa một bản sao của giá trị cũ khỏi khối đã sắp xếp, rồi chèn giá trị mới vào đúng chỗ. Cập nhật cả dãy ban đầu. Khi có nhiều giá trị bằng nhau, chỉ xóa một phần tử.

Độ phức tạp

Dựng các khối tốn \(O(N\log B)\). Một truy vấn đếm tốn \(O(B+(N/B)\log B)\) trong trường hợp xấu nhất; một thao tác gán tốn \(O(B)\) do dịch phần tử trong khối. Bộ nhớ là \(O(N)\).

Lời giải C++ tham khảo dùng \(B=700\). Tìm vị trí đầu tiên có giá trị \(\ge c\) bằng lower_bound; upper_bound sẽ bỏ qua những phần tử bằng \(c\).

Phương án Fenwick cho Python

Lời giải Python tham khảo dùng một cây Fenwick trên các vị trí. Mỗi nút của cây lưu thêm một Fenwick đếm các giá trị trong đoạn mà nút đó quản lý.

Đọc trước các thao tác để biết những giá trị có thể được gán tại mỗi vị trí. Đưa các giá trị ban đầu và giá trị cập nhật vào những nút chứa vị trí đó. Trong mỗi nút, sắp xếp và bỏ các giá trị trùng nhau; thứ tự còn lại dùng làm chỉ số cho cây đếm bên trong.

Khi gán một phần tử, đi qua các nút chứa vị trí đó, bớt một lần xuất hiện của giá trị cũ rồi thêm một lần xuất hiện của giá trị mới. Để đếm những giá trị nhỏ hơn \(c\) trong một tiền tố, duyệt các nút Fenwick phủ tiền tố đó và lấy tổng tần suất trước vị trí bisect_left(c) trong từng nút.

Gọi \(F(r,c)\) là số phần tử nhỏ hơn \(c\) trong \([1,r]\), với \(F(0,c)=0\). Đáp án cần tìm là:

Với \(U\) thao tác gán, đặt \(K=N+U\). Mỗi giá trị được lưu vào \(O(\log(N+1))\) nút. Tiền xử lý tốn \(O(K\log(N+1)\log(K+1))\); mỗi thao tác tốn \(O(\log(N+1)\log(K+1))\). Bộ nhớ là \(O(K\log(N+1))\). Mã Python lưu các bảng giá trị và tần suất trong hai mảng số nguyên liên tiếp để giảm chi phí của nhiều danh sách nhỏ.