线段树

学习。

首先,记住这个图(from Woziji):

仅需要单点修改时可以不用 lazy tag。

Eg1:维护最大值,单点修改,区间查询。最大数 - AcWing

Eg2:维护区间最大子段和,单点修改,区间查询。你能回答这些问题吗 - AcWing

Eg3:维护区间最大公约数,区间修改,区间查询。区间最大公约数 - AcWing
(本题维护差分数组实现区间修改)

使用 lazy tag 实现区间修改区间查询。

Eg1:维护区间和,区间修改,区间查询。一个简单的整数问题2 - AcWing