Bài này sử dụng segment tree kết hợp với lazy propagagion (lan truyền lười) hay cập nhật lười, tức trong quá trình update cây, ta sẽ tránh duyệt sâu vào từng node lá của cây mà sẽ chỉ cập nhật các node khi cần đi đến, những node con cần được cập nhật sẽ được lưu vào một mảng để sau này cập nhật nếu dùng đến. Các bạn có thể search từ khóa lazy propagation in segment tree hay lazy update in segment tree để hiểu sâu hơn về kĩ thuật này.

Tạo một mảng lazy[] cho mỗi một node của cây segment. Mỗi khi có thao tác đụng đến node nào đó, ta sẽ cần cập nhật lai node đó từ mảng lazy[] này. Cụ thể khi có thao tác tăng đoạn hay tìm max, khi duyệt đến node k trong cây segment, ta cập nhật lại giá trị tại node này nếu giá trị lazy[k] cho biết trước đó các node cha đã cập nhật và lan truyền lười cho nó. Nhận xét trong bài này, khi tăng đoạn con lên một giá trị dương k, giá trị lớn nhất trên đoạn đó cũng tăng lên luợng k. Do đó mảng lazy lưu lại số luợng được tăng cho node của cây. Khi node nào đó được tăng lên k, ta cập nhật giá trị tại node đó, đồng thời cập nhật giá trị này cho các node con thông qua mảng lazy. Khi các node con trong tương lai được gọi đến, giá trị trên mảng lazy sẽ được dùng để cập nhật, đônồ thời truyền xuống cho các node cháu (node con của các node con này).