Sub1: Có thể trâu = nhiều cách, không cần prefix sum
Sub2: Dùng vòng lặp for với mỗi a(i) sao cho i thuộc đoạn [u, v], tăng a(i) lên c rồi tính tổng tiền tố p(i) của mảng a(i) sau khi đã tăng, đáp án là max(p(i)) - min(p(i)). Độ phức tạp O(N x Q)
Sub3: Quan sát mảng tổng tiền tố p(i) sau khi tăng đoạn [u, v] lên c, đoạn [1, u - 1] không thay đổi, đoạn [u, v] tăng (i - u + 1) x c với i thuộc [u, v], đoạn [v + 1, n] tăng (v - u + 1) x c. Dùng 1 vòng for từ u -> v để tìm max(p(i)) và min(p(i)), 2 đoạn còn lại dùng mảng tiền tố, hậu tố Min và Max để xét trong O(1). Độ phức tạp O(N x S) với S là tổng của v - u + 1 với mọi truy vấn
Sub4: Biến đổi p(i) + (i - u + 1) x c = p(i) + c x i - (u - 1) x c, đặt A = i, B = p(i) - (u - 1) x c, việc tìm max(p(i)) và min(p(i)) trong đoạn [u, v] trở thành tìm (A, B) sao cho A x c + B là lớn nhất, nhỏ nhất với A thuộc đoạn [u, v]. Sử dụng Convex Hull Trick để có thể giải quyết bài toán trên, áp dụng thêm Segment Tree với các nút là CHT để có thể tìm riêng trong các đoạn [u, v]. Độ phức tạp O(N x log x log) hoặc O(N x log)
Link tham khảo về Convex Hull Trick: https://vnoi.info/wiki/translate/wcipeg/Convex-Hull-Trick