遅延更新操作と通常の更新操作を対比し、これがクエリ操作をどのように変更するかを説明します。
通常の単一の更新操作では、ツリーのルートを更新してから、ツリーの必要な部分のみを再帰的に更新します (したがって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));
}