algorithm - セグメント化されたツリーの遅延伝播

Question

セグメント化されたツリーの遅延伝播アルゴリズムには、私には不明な点があります。以下のコードによると、クエリ間隔が完全にオーバーラップすると、更新値が親ノードに追加され、子は遅延更新用にマークされます。しかし、添付の画像でわかるように、範囲 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}

問題は、0,1 からの合計を求めるクエリが +4 更新後に呼び出された場合はどうなるかということです。

Answer 1

まず、実装の目的は 2 つの操作を提供することのようです。

1. v範囲内のすべての要素の値を増やす[i, j]
2. max範囲の値を照会します[i, j](最後の行からわかります)

範囲の合計をクエリすることについて質問していますが、これはおそらく更新方法では不可能ですtree[node]。

update次に、関数と関数の両方から遅延伝播を使用する必要がありqueryます。

maxrange の値を照会しようとしていると仮定します[i, j]。おそらく次のようなコードを取得する必要があります。

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));
}

Answer 2

わかりました、そのリンクの合計の遅延伝播でセグメント ツリーを更新する正しい方法を見つけました。

合計の遅延伝播