我将惰性更新操作与正常更新操作进行对比，以及这如何改变查询操作。
在正常的单个更新操作中，您更新树的根，然后递归地仅更新树的所需部分（从而为您提供O(log(n))速度）。如果您尝试对范围更新使用相同的逻辑，您可以看到它如何恶化O(n)（考虑非常广泛的范围，并看到您主要需要更新树的两个部分）。
因此，为了克服这个O(n)想法，只有在您真正需要时才更新树（查询/更新先前更新的段，从而使您的更新变得懒惰）。所以这是它的工作原理：
- 树的创建完全一样。唯一的细微差别是您还创建了一个数组，其中包含有关潜在更新的信息。
- 当你更新树的节点时，你还要检查它是否需要更新（从之前的更新操作），如果是 - 你更新它，标记孩子将来要更新并取消标记节点（懒惰）
- 当您查询树时，您还检查节点是否需要更新，如果需要更新它，将其标记为子节点并在之后取消标记。
下面是一个更新和查询的例子（解决最大范围查询）。如需完整代码，请查看本文。
void update_tree(int node, int a, int b, int i, int j, int value) {
if(lazy[node] != 0) { // This node needs to be updated
tree[node] += lazy[node]; // Update it
if(a != b) {
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a > b || a > j || b < i) // Current segment is not within range [i, j]
return;
if(a >= i && b <= j) { // Segment is fully within range
tree[node] += value;
if(a != b) { // Not leaf node
lazy[node*2] += value;
lazy[node*2+1] += value;
}
return;
}
update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}
和查询：
int query_tree(int node, int a, int b, int i, int j) {
if(a > b || a > j || b < i) return -inf; // Out of range
if(lazy[node] != 0) { // This node needs to be updated
tree[node] += lazy[node]; // Update it
if(a != b) {
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a >= i && b <= j) // Current segment is totally within range [i, j]
return tree[node];
return max(query_tree(node*2, a, (a+b)/2, i, j), query_tree(1+node*2, 1+(a+b)/2, b, i, j));
}