Bài gợi ý: Liên Minh Dễ Dàng
Tóm tắt: Cho dãy \(a_1, a_2, \dots, a_n\). Ta cần xử lý thao tác gán \(a_i = x\) và tìm phong độ ban đầu nhỏ nhất để lần lượt thắng các trận từ \(l\) đến \(r\). Tại mỗi trận \(k\), phong độ hiện tại phải đạt tối thiểu \(a_k\), rồi được cộng thêm \(a_k\).

Xét ví dụ với ba trận có chỉ số \(2, 10, 5\). Nếu bắt đầu với \(8\) điểm, bạn hạ trận đầu và có \(8 + 2 = 10\) điểm. Mức này vừa đủ thắng trận hai để đạt \(20\) điểm, rồi vượt qua trận cuối. Nếu chỉ bắt đầu với \(7\) điểm, bạn xong trận đầu chỉ có \(9\) điểm và sẽ thua ở trận thứ hai.

Ta đang lặp lại phép tính nào khi ghép các trận liên tiếp? Giả sử đoạn bên trái cần phong độ tối thiểu \(L.req\) và tăng thêm \(L.sum\) điểm. Để đủ \(R.req\) điểm khi bước sang đoạn bên phải, bạn cần chuẩn bị sẵn ít nhất \(R.req - L.sum\) điểm trước khi vào đoạn trái.

Vì vậy, mỗi đoạn con chỉ cần lưu hai đại lượng: tổng phong độ \(sum\) và mức khởi đầu tối thiểu \(req\). Khi gộp hai đoạn kề nhau, giá trị mới được tính theo \(req = \max(L.req, R.req - L.sum)\) cùng \(sum = L.sum + R.sum\).

Cách duyệt trực tiếp từng phần tử sẽ mất nhiều thời gian cho mỗi truy vấn khi \(q\) lớn. Do phép gộp trên có tính kết hợp, cây phân đoạn (Segment Tree) là cấu trúc phù hợp để quản lý và cập nhật từng vị trí.

Khi cài đặt, mỗi nút lá ứng với phần tử \(a_i\) được gán sum = a_i và req = a_i. Khi truy vấn đoạn \([l, r]\), bạn lần lượt gộp các nút đại diện và lấy trường req của kết quả cuối cùng.