algorithm - 序列的数据结构

Question

我正在训练数据结构的测试，但我无法解决这个问题：

设计一个保持序列 a_1, ..., a_n 的数据结构，并且可以对其执行两个操作：

1. 将 a_i 设置为值 x
2. 计算值 x 在两个索引之间的序列中出现的次数：i 和 j；只是为了确保我说清楚（我不擅长英语），这意味着返回|{a_k: a_k = x and i <= k <= j}|给定的：x，i，j。

约束：

• a_i 来自区间 [0, ..., 10^9]，
• n 更小 - 它小于 10^5

这两个操作最多应该在 O(log n) 时间内工作。不幸的是，我看到它的唯一方法是 O(log^2 n)。我们使用 in 节点保留区间树maps<int,int>，它计算 x 在子树中出现的次数。同样重要的是不要保留出现 0 次的映射值（内存复杂度）。

我怎样才能更好地解决它？任何人都可以帮忙吗？

Answer 1

这是具有两个数据字段的 BST：

BSTNode<E>{
   int index;
   E value;
   BSTNode left, right;
}

按索引对树排序，以便搜索为 O(lg n)：这有助于插入和设置 ( seta_i to value x)。

至count how many times value x occurs in a sequence between two indexes: i, j

• 找到 i 和 j 的直接公共父级：http ://www.geekviewpoint.com/java/bst/immediate_common_parent
• 然后遍历以公共父节点为根的子树：对于每次访问，只计算值为 的节点x。这类似于总结单身儿童http://www.geekviewpoint.com/java/bst/sum_single_children或按顺序访问树叶（来自同一站点）。

编辑：

i在找到and的公共父节点后j，可以简单地查找一个值的频率，而不是遍历子树：每个节点（这里是 commonParent）可以有一个频率图：Map<E,Integer> childrenFreq = new HashMap<E,Integer>()。一旦在 O(lg n) 中找到共同的父母，这将是 O(1)