线段树·懒标记直觉

10 分钟

区间修改若逐个改叶子会退化成 O(n)。懒标记(lazy)的思路是:给某节点整段打一个“待办”标记,先更新它自身的汇总值,暂不下传给孩子;等真要访问孩子时再下放。这样区间修改也能 O(log n)。

小纸条

打了懒标记的节点,它的孩子此刻是最新的吗?

登录 后可看答案