このSplay Treeの範囲の合計がより高速に実装されていますか？

Question

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

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という名前の次の関数を実装しsummation関数を呼び出す前に0に初期化されるグローバルint変数です。 2つのパラメータst は、範囲（両端を含む）を定義します。

summation関数は、O（n）の複雑さで機能します。誰もこれのための任意の高速実装を提案することはできますか？

Answer 1

これは、私はいくつかの時間前にやったスプレー木の実装であり、（C++で書かれた）SPOJ評価システムに対してテスト：

https://ideone.com/aQgEpF

このツリーの実装では、uは（範囲を求めているものをサポートしています合計でO(log(n))。

ここでの重要なアイデアは、範囲をカバーするサブツリーを抽出するためにsplitとmergeを使用することです。さらに、各ノードには、すべてのキーiの合計であるフィールドsum nそのサブツリー。 sumフィールドは遅延評価され、分割操作中（分割線に沿って）にのみ中継されるため、計算する必要のないレベルまで深く進まないようにすることができます。

Answer 2

最初に、副注釈として、summationが何も返さず、グローバル変数を操作する代わりに、probably not such a great ideaです。このグローバル変数を省略し、再帰関数で見つかったものだけを返すようにしてください（そして、この合計を返す前に、呼び出しはさらに再帰呼び出しによって返される値を合計します）。

具体的な質問については、合計操作をaugmenting node metadataで最適化することができます。これにより、他の操作の成長順序に影響を与えることなく、総和操作の成長の順序が減少します。欠点として、これは他の操作の速度をやや低下させます。このトレードオフがあなたのために良いのかどうかはあなた次第です。次のように

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

1. このノードをルートとするツリー内の項目の合計を示す、各ノード内の別のフィールドを保ちます。

2. いくつかの考えでは、ツリーを更新するときにこの情報を効率的に更新する方法がわかります。

3. さらに、このメタデータを使用して範囲クエリに答える方法を確認できます。