3

スプレイツリーをコーディングしました。ノードはこのように表されます。

struct Node{
    Node *l;  /// The left  Node
    Node *r;  /// The right Node
    int v;    /// The Value
};

ここで、特定の範囲内のツリー内のすべての数値の合計を知る必要があります。このために、次の名前の関数を実装しましたsummation.

void summation(Node *R, int st, int ed)
{
    if(!R) return;
    if(R->v < st){        /// should not call left side
        summation(R->r, st, ed);
    }
    else if(R->v > ed){   /// should not call right side
        summation(R->l, st, ed);
    }
    else{                /// should call both side
        ret+=R->v;
        summation(R->l, st, ed);
        summation(R->r, st, ed);
    }
    return;
}

ret関数を呼び出す前に初期化されるグローバルint変数です。2 つのパラメーター&は範囲 (包括的) を定義します。0summationsted

このsummation関数は、O(n) の複雑さで機能します。誰でもこれのより速い実装を提案できますか??

4

2 に答える 2

4

これは、私が少し前に実行し、SPOJ 評価システム (C++ で記述) に対してテストしたスプレイ ツリーの実装です。

https://ideone.com/aQgEpF

このツリーの実装は、あなたが求めているものをサポートしています (range sum in O(log(n)).

ここでの重要なアイデアは、分割とマージを使用して、範囲をカバーするサブツリーを抽出することです。さらに、各ノードにはsum、そのサブツリー内のすべてのキーの合計である フィールド が含まれています。フィールドは遅延評価され、sum分割操作中にのみ中継されます (分割線に沿って)。これにより、計算する必要のないレベルに深く入ることができなくなります。

于 2016-08-08T09:21:14.883 に答える
1

まず、補足として、summation何も返さずに代わりにグローバル変数を操作することは、おそらくあまり良い考えではありません。おそらく、このグローバル変数を省略することを検討し、再帰関数が見つけたものだけを返すようにする必要があります (この合計自体を返す前に、さらなる再帰呼び出しによって返された値を合計する呼び出しを行う必要があります)。

特定の質問に関しては、node metadataを拡張することで合計操作を最適化できます。これにより、他の操作の増加の順序に影響を与えることなく、合計操作の増加の順序が減少します。欠点として、これにより他の操作の速度が多少低下します。このトレードオフが良いかどうかは、あなた次第です。

基本的な考え方は次のとおりです。

  1. 各ノード内に、このノードをルートとするツリー内のアイテムの合計を示す別のフィールドを保持します。

  2. 少し考えれば、ツリーを更新するときにこの情報を効率的に更新する方法がわかります。

  3. さらに考えてみると、このメタデータを使用して範囲クエリに答える方法がわかります。

于 2016-08-08T08:36:32.930 に答える