Bài gợi ý: Tìm dãy con có tổng lớn nhất 2
Tóm tắt: Bạn có một dãy gồm \(N\) số nguyên. Bạn cần xử lý hai loại thao tác: thay đổi giá trị một phần tử, hoặc tìm tổng đoạn con liên tiếp lớn nhất thuộc đoạn từ \(l\) đến \(r\).

Xét dãy 5 phần tử ban đầu 1 2 -3 4 5. Với truy vấn trên đoạn từ \(1\) đến \(3\), đoạn con [1, 2] cho tổng lớn nhất bằng \(3\). Sau đó, nếu cập nhật phần tử đầu thành \(-100\), đoạn \([1, 3]\) trở thành -100 2 -3. Khi đó, kết quả tốt nhất trên đoạn này chỉ còn là \(2\).

Nếu mỗi lần truy vấn ta duyệt lại toàn bộ đoạn \([l, r]\), mỗi thao tác mất tới \(O(N)\) bước. Với \(N \le 5 \cdot 10^4\) và \(M \le 5 \cdot 10^4\), tổng số thao tác có thể lên tới \(2.5 \cdot 10^9\) phép tính. Cách làm này sẽ vượt quá thời gian cho phép.

Giả sử ta chia một đoạn thành hai nửa trái và phải. Đoạn con có tổng lớn nhất chỉ có thể rơi vào ba trường hợp: nằm gọn ở nửa trái, nằm gọn ở nửa phải, hoặc băng qua ranh giới giữa hai nửa. Muốn tính trường hợp băng qua ranh giới, ta cần lấy hậu tố lớn nhất của nửa trái cộng với tiền tố lớn nhất của nửa phải.

Cây phân đoạn (Segment Tree) giúp ta duy trì phép gộp này rất hiệu quả. Mỗi nút của cây quản lý một đoạn và lưu 4 giá trị: tổng cả đoạn sum, tiền tố lớn nhất pref, hậu tố lớn nhất suff, và đoạn con lớn nhất ans. Khi gộp nút con trái và nút con phải, ta cập nhật:
\(ans = \max(\{left.ans, right.ans, left.suff + right.pref\})\),
\(pref = \max(left.pref, left.sum + right.pref)\),
\(suff = \max(right.suff, right.sum + left.suff)\),
cùng với tổng cả đoạn \(sum = left.sum + right.sum\).

Khi cài đặt, bạn có thể kiểm tra từng phần:

• Nút lá tại vị trí \(x\) khởi tạo cả bốn giá trị sum, pref, suff, ans đều bằng giá trị tại vị trí đó.
• Hàm update(id, l, r, pos, val) đi xuống đúng lá pos, thay đổi giá trị rồi gộp ngược lên gốc.
• Hàm query(id, l, r, u, v) trả về một nút chứa đủ 4 thông tin của phần giao giữa đoạn truy vấn và đoạn của nút.

Bài tập tương tự:

• CSES - Subarray Sum Queries | Truy vấn tổng đoạn con: Luyện tập thao tác cập nhật điểm và lấy kết quả lớn nhất trên toàn dãy.
• Đoạn con có tổng lớn nhất: Luyện kỹ năng viết hàm truy vấn đoạn con trên cây phân đoạn mà không có thao tác cập nhật.

Bạn chỉ cần dựng hàm gộp hai nút merge(left, right), gọi update(1, 1, n, x, y) cho thao tác loại 1, và in ra trường ans của nút kết quả từ query(1, 1, n, l, r) cho thao tác loại 2.