这个 Splay Tree range sum 有没有更快的实现?

Is there any faster implementation for this Splay Tree range sum?

我编写了一个 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 函数之前被初始化为 0st & ed 两个参数定义范围(含)。

summation 函数的工作复杂度为 O(n)。谁能为此提出任何更快的实施建议?

首先,作为旁注,summation 而不是 return 任何东西,而不是操纵全局变量,是 probably not such a great idea。您可能应该考虑省略此全局变量,并让递归函数仅 return 它找到的内容(并在 return 之前通过其进一步的递归调用对值 return 求和计算这个总和本身)。

针对你的具体问题,可以通过augmenting node metadata优化求和运算。这将降低求和运算的增长顺序,而不影响其他运算的增长顺序。不利的一面是,这会在一定程度上降低其他操作的速度。由您决定这种权衡是否对您有利。

基本思路如下:

  1. 在每个节点中保留另一个字段,指示以该节点为根的树中项目的总和。

  2. 稍加思索,就可以看出在更新树的时候如何高效的更新这些信息了。

  3. 经过进一步思考,您可以了解如何使用此元数据回答范围查询。

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

https://ideone.com/aQgEpF

此树实现支持您的要求(O(log(n)) 中的范围总和。

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