c++ - 数列から数を引いた後、残りの数のうち正の数はいくつですか?

Answer 1

データ構造

データ構造の遅延伝播を伴うセグメント ツリーを使用します。

各ノードストアで:

1. すべての子ノードの正の値の数
2. すべての子ノードの最小の正の値 (つまり、値が -1、3、5、-10 の子の最小の正の値は 3 です。-1 と -10 は正ではないため無視します。)
3. このノードから減算する保留中の値 (0 に初期化)

アップデート

範囲を更新する手順は次のとおりです。

1. 範囲に完全に含まれるノードが見つかるまで、セグメント ツリーを再帰的に下ります。
2. ノードの保留値を変更します

クエリ

範囲のクエリに回答する手順は次のとおりです。

1. 範囲に完全に含まれるノードが見つかるまで、セグメント ツリーを再帰的に下ります。
2. ノードの保留中の値が正の最小値より大きい場合、ノードのプロパティを再帰的に更新します

複雑

各ノードが負になるのは 1 回だけなので、この手順全体は O(nlogn+qlogn) である必要があると思います。ここで、n はシーケンスの長さ、q は操作の数です。

例

配列 [1,5,-3,4] があるとします。

次のようなセグメント ノードがあります。

[1,5,-3,4] min positive 1, pending change 0
[1,5] min positive 1, pending change 0
[-3,4] min positive 4, pending change 0

範囲全体を 2 の減算で更新したいとします。これを次のように変更します。

[1,5,-3,4] min positive 1, pending change 2.

ここで、保留中の変更が >= 最小正であるため、変更を左の子と右の子に再帰的にプッシュしてノードを修正する必要があります。

まず、左の子は次のように変更されます。

[1,5] min positive 1, pending change 2

次に、このノードを再度展開し、更新を適用して次のようにします。

[-1,3] min positive 3, pending change 0

次に、次のように変更される右の子に移動します。

[-3,4] min positive 4, pending change 2

しかし、保留中の変更 < 正の最小値であるため、それ以上の再帰は必要ありません。

最後に、再帰は再び最上位ノードに到達します。左と右の子のプロパティを使用して、最小陽性が 2 であることを計算します (最小 4 の右の子と保留中の 2 から 4-2=2 の結果が得られます)。保留中の変更を 0 にリセットできます。それは子供たちに適用されたからです。

Answer 2

コーディングしやすいデータ構造は、セグメント ツリーと呼ばれます。
高速だがコーディングが難しいデータ構造は、Binary-indexed-tree と呼ばれます。