范围查询树中的路径-Java 学习之路

我在竞赛中遇到了这个问题（现在已经结束了），我无法想到一个节省时间的算法 .

您将获得一个有根节的N（<= 10 ^ 5）个节点 . 最初，所有节点都具有值0.对于树的M个更新（<= 10 ^ 5）是形式的

添加x y - 将y添加到节点x .

AddUp x y - 将y添加到x，x的父级，x uptill Root的父级的父级 .

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

我做了什么：-

首先，我尝试了根据操作更新每个节点的朴素算法，但显然需要时间 .

我还想过使用段树和懒惰传播，但想不出一个正确的方法 .

任何帮助表示赞赏，谢谢！

3 回答

1
首先，构建一个孩子指向父母的图表 . 之后，解析所有更新并分别在树的每个节点中存储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.
```
现在，使用拓扑顺序横切图形，即，如果已经处理了所有子节点，则只处理节点，这需要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 .
回复于 2024-05-03T14:32:29+08:00
1
这是一个Fenwick树，为了解决这类问题，您必须在树上执行拓扑排序并计算每个节点的子项数 .
```
0
    /   \
   1     2
  / \
 3   4
```
index：[0 1,2,3,4] childrenrens：[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树，您可以执行2种查询，更新查询，范围求和查询，当您需要更新仅索引调用 update(pos[index], y) 时，则必须减少所有下一个值， update(pos[index]+1, -y) 当您需要更新所有父项时，请调用 update(pos[index], y) 和 update(pos[index] + childrens[index] + 1, -y);

知道你需要在pos [index]上调用范围和查询的位置值
回复于 2024-05-03T14:32:29+08:00

我认为这个问题只是二进制搜索树的直接应用，对于插入和查询，它具有平均情况成本（在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 .

回复于 2024-05-03T14:32:29+08:00

范围查询树中的路径

3 回答

相关问题