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被初始化。&两个参数定义范围（包括）。0summationsted

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

4

2 回答 2

4

这是我前段时间所做的展开树实现，并针对 SPOJ 评估系统（用 C++ 编写）进行了测试：

https://ideone.com/aQgEpF

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

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

于 2016-08-08T09:21:14.883 回答
1

首先，作为旁注，summation不返回任何内容，而是操作全局变量，可能不是一个好主意。您可能应该考虑省略这个全局变量，并让递归函数只返回它找到的内容（并在返回这个总和之前，调用对其进一步递归调用返回的值进行求和）。

关于您的具体问题，您可以通过增加节点元数据来优化求和操作。这将降低求和运算的增长顺序，而不会影响其他运算的增长顺序。不利的一面是，这会在一定程度上降低其他操作的速度。由您决定这种权衡是否对您有利。

基本思路如下：

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

  2. 经过一番思考，您可以看到在更新树时如何有效地更新此信息。

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

于 2016-08-08T08:36:32.930 回答