Đầu tiên, chúng ta thử giải bài toán với trường hợp không có cập nhật. Với một dãy \(a_1, a_2, ..., a_n\), ta dựng 2 dãy sau:

• \(s_i = a_1 + a_2 + ... + a_i\)
• \(b_i = a_i - s_{i - 1}\)

Khi đó đáp số là \(max(b_1, b_2, ..., b_n)\). Chứng minh này khá đơn giản, xin nhường lại các bạn.

Với một truy vấn \((l, r)\) thì chúng ta làm thế nào? Đáp số sẽ là \(max(b_l, b_{l+1}, ..., b_r) - s_{l - 1}\).

Do vậy để làm subtask \(2\), các bạn có thể dùng RMQ để trả lời các truy vấn max cho một đoạn.

Subtask 3:

Để giải subtask cuối, chúng ta cần quan tâm thao tác cập nhật \(a_x = y\). Điều cần quan tâm là thao tác này sẽ làm biến đổi dãy \(b\) và \(s\) như thế nào?

• Dãy \(s\) có thể dễ dàng cập nhật bằng BIT / Fenwick Tree
• \(b_x\) tăng lên \(y - a_x\) đơn vị
• \(b_i\) tăng lên \(a_x - y\) đơn vị \(\forall i > x\)

Như vậy chúng ta cần thao tác tăng các số trong một đoạn lên \(k\) đơn vị và lấy max của một đoạn. Đây chính là ứng dụng cơ bản của Segment Tree + Lazy Propagation (Cây IT + Cập nhật Lazy).

Độ phức tạp: \(O((n + q) \log n)\)