分段树的惰性传播
Lazy propagation for Segmented Tree
分段树的惰性传播算法中有一些我不清楚的地方。根据下面的代码,在查询间隔完全重叠时,更新值只是添加到父节点,子节点被标记为惰性更新。但是正如您在附图中看到的那样,如果对范围 0,1 进行 +4 更新,则两棵树的结果完全不同! (左图:没有惰性传播)。
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}
所以问题是,如果在 +4 更新后调用从 0,1 求和的查询怎么办?
首先,您的实现目的似乎是为 2 个操作服务。
- 为范围
[i, j]
中的所有元素增加值 v
- 查询范围
[i, j]
的max
值(我从最后一行看到的)
您询问的是查询范围的总和,这可能无法通过您更新 tree[node]
的方式实现。
其次,您应该使用 update
函数和 query
函数的惰性传播。
我假设您正在尝试查询范围 [i, j]
的 max
值。您可能会得到这样的代码:
int query_max(int node, int a, int b, int i, int j) {
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 -INFINITY;
}
if(a >= i && b <= j) { // Segment is fully within range
return tree[node];
}
return max(query_max(node*2, a, (a+b)/2, i, j), query_max(node*2+1, a, (a+b)/2+1, i, j));
}
好的,我找到了一种正确的方法来更新线段树,其中包含延迟传播求和 link。
分段树的惰性传播算法中有一些我不清楚的地方。根据下面的代码,在查询间隔完全重叠时,更新值只是添加到父节点,子节点被标记为惰性更新。但是正如您在附图中看到的那样,如果对范围 0,1 进行 +4 更新,则两棵树的结果完全不同! (左图:没有惰性传播)。
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}
所以问题是,如果在 +4 更新后调用从 0,1 求和的查询怎么办?
首先,您的实现目的似乎是为 2 个操作服务。
- 为范围
[i, j]
中的所有元素增加值 - 查询范围
[i, j]
的max
值(我从最后一行看到的)
v
您询问的是查询范围的总和,这可能无法通过您更新 tree[node]
的方式实现。
其次,您应该使用 update
函数和 query
函数的惰性传播。
我假设您正在尝试查询范围 [i, j]
的 max
值。您可能会得到这样的代码:
int query_max(int node, int a, int b, int i, int j) {
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 -INFINITY;
}
if(a >= i && b <= j) { // Segment is fully within range
return tree[node];
}
return max(query_max(node*2, a, (a+b)/2, i, j), query_max(node*2+1, a, (a+b)/2+1, i, j));
}
好的,我找到了一种正确的方法来更新线段树,其中包含延迟传播求和 link。