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