セグメント ツリー構造を使用して、配列内の特定の値の頻度を計算する方法はありますか?
サイズ N の配列 A があり、配列のすべての要素 A[i] に値 0、1、または 2 が含まれているとします。次の操作を実行します。
- 配列の任意の範囲 [a,b] のゼロの量を計算します
- 配列の任意の範囲 [a,b] 内のすべての要素をインクリメント (mod 3) します
例: A = [0,1,0,2,0] の場合:
- [2,4] の範囲には 0 が 1 つあるため、Query[2,4] は 1 を返す必要があります。
- Incre[2,4] は、A を [0,2,1,0,0] に更新します。
これは、セグメント ツリーを使用して解決できる (この場合は、範囲の更新のために遅延伝播を使用する) 範囲合計クエリの問題によく似ていますが、セグ ツリー コードをこの問題に適応させることに成功しませんでした。通常の RSQ のようなツリー内の値では、値「3」を含む親ノード (たとえば) は何も意味しません。この情報では、この範囲に存在するゼロの数を抽出できないためです。
前もって感謝します！
--
編集：
セグメント ツリーは、配列に関連する区間をそのノードに格納するバイナリ ツリー構造です。葉ノードは実際の配列セルを格納し、各親ノードはその子の関数 f(node->left, node->right) を格納します。セグメント ツリーは、配列の範囲 [a,b] 内のすべての要素の合計を計算する範囲合計クエリを実行するためによく使用されます。この場合、親ノードによって計算される関数は、その子ノードの値の合計です。範囲合計クエリの問題を解決するためにセグツリーを使用したいのは、O(log n) で解決できるためです (範囲クエリで完全にカバーされるノードが見つかるまでツリーを下るだけです)。単純な O(n) アルゴリズム。