序列的数据结构

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).我们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和j,而不是遍历子树,可以简单地查找一个值的频率:每个节点(这里是commonParent)可以有一个频率图:Map<E,Integer> childrenFreq = new HashMap<E,Integer>().一旦在O(lg n)中找到共同父项,这将是O(1)