c - 这个 Splay Tree range sum 有没有更快的实现？

Question

我编写了一个 splay 树。节点是这样表示的。

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 变量，在调用 summation 函数之前被初始化为 0。 st 和 ed 这两个参数定义了范围(包括)。

summation 函数的复杂度为 O(n)。任何人都可以为此建议更快的实现吗？

Answer 1

这是我前一段时间做的拉伸(stretch)树实现，并针对 SPOJ 评估系统(用 C++ 编写)进行了测试:

https://ideone.com/aQgEpF

这个树实现支持你所要求的(O(log(n)) 中的范围总和。

这里的关键思想是使用拆分和合并，提取覆盖范围的子树。此外，每个节点都包含一个字段 sum，它是其子树中所有键的总和。 sum 字段是惰性求值的，仅在拆分操作期间(沿着拆分线)进行中继，这不允许更深入到不需要计算的级别。