树中路径的范围查询

Question

我在一次比赛中遇到了这个问题（现在已经结束），我想不出一个节省时间的算法。

给你一棵 N ( <=10^5) 个节点的有根树。最初所有节点的值 0.There 将是树的 M 更新 (<=10^5)，其形式为

Add x y – 将 y 添加到节点 x 。

AddUp x y – 将 y 添加到 x，x 的父级，x 的父级的父级，直到根。

之后会有 Q 个查询（<=10^5）个查询，您将被要求提供节点的值或以该节点为根的子树的总和。

我做了什么：-

首先我尝试了根据操作更新每个节点的朴素算法，但显然这很花时间。

我也想过使用线段树和惰性传播，但想不出合适的方法。

感谢任何帮助，谢谢！

Answer 1

首先，构建一个图，其中 children 指向它们的 parents。之后，解析所有更新并将 Add 和 AddUp 的总和分别存储在树的每个节点中。您的节点应具有以下变量：

sum_add : the sum of all the Add of this node
sum_add_up : the sum of all the AddUp of this node
subtree_sum : the sum of the subtree. Initialize with 0 by now.

现在，使用拓扑顺序横向处理您的图，即，如果节点的所有 children 都已被处理，您将只处理一个节点，这需要 O(N)。现在让我定义过程函数。

process(V) {
    V.sum_add_up = V.sum_add_up + sum(sum_add_up of all V.children)
    V.subtree_sum = V.sum_add + V.sum_add_up + sum(subtree_sum of all V.children)
}

现在您可以在 O(1) 中回答所有问题。查询一个节点V的值是V.sum_add + V.sum_add_up，查询V的子树就是V.subtree_sum.

Answer 2

我认为这个问题只是二叉搜索树的直接应用，它具有平均情况成本（在 n 次随机操作之后）O(1.39log(n)) 对于插入和查询。

您所要做的就是递归地添加新节点并同时更新值和求和。

实现也相当简单（对不起 C#），例如 Add()（AddUp() 类似 - 每次转到左子树或右子树时增加值）：

public void Add(int key, int value)
{
    Root = Add(Root, key, value);
}

private Node Add(Node node, int key, int value)
{
    if (node == null)
    {
        node = new Node(key, value, value);
    }

    if (key < node.Key)
    {
        node.Left = Add(node.Left, key, value);
    }
    else if (key > node.Key)
    {
        node.Right = Add(node.Right, key, value);
    }
    else
    {
        node.Value = value;
    }

    node.Sum = Sum(node.Left) + Sum(node.Right) + node.Value;

    return node;
}

对于我机器上的 100000 个数字，这将转换为这些数字：

Added(up) 100000 values in: 213 ms, 831985 ticks
Got 100000 values in:       86 ms, 337072 ticks

对于 100 万个数字：

Added(up) 1000000 values in: 3127 ms, 12211606 ticks
Got 1000000 values in:       1244 ms, 4857733 ticks

这个时间够不够高效？您可以尝试完整的代码 here.

Answer 3

这是一棵分域树，为了解决这类问题，您必须对树进行拓扑排序，并计算每个节点的子节点数。

索引：[0 1,2,3,4] 儿童：[4,2,0,0,0] 使用拓扑，您将获得此向量 0 1 3 4 2 您需要将其反转：

fenwick Pos:  [0,1,2,3,4]
vector values:[2,4,3,1,0]
pos: [5,3,0,2,1]

使用fenwick tree你可以执行2种查询，update query, range sum query 当您只需要更新一个索引调用 update(pos[index], y) 时，您必须减少所有下一个值 update(pos[index]+1, -y) 当您需要更新所有父项时调用 update(pos[index], y) 和 update(pos[index] + childrens[index] + 1, -y);

要了解位置的价值，您需要调用 pos[index] 上的范围求和查询

树中路径的范围查询

Range Queries on a path in a tree

c++

algorithm

tree

path

segment-tree