相关疑难解决方法(0)

Fenwick树是一种允许两种操作的数据结构(您可以通过更多操作来扩充它):

• 点更新 update(index, value)
• 前缀总和 query(index)

两个操作都是在O(log(n))其中n是一个数组的大小.理解如何进行操作及其背后的逻辑,我没有任何问题.

我的问题是如何从数组初始化Fenwick树.很明显,我可以O(nlog(n))通过调用n时间来实现这一点update(i, arr[i]),但有没有办法将其初始化O(n).

如果维基百科告诉您可以初始化,我为什么要问这个nlog(n)？因为这篇文章是如此简陋,我不确定它是否是人们能够实现的最佳复杂性.还可以通过逐个填充堆来完成与初始堆创建的相似之处,并且可以在O(nlog(n))智能堆初始化中实现O(n),这使我希望在Fenwick树中可以完成类似的操作.

今天我听了关于fenwick树(二进制索引树)的讲座,老师说这个树是区间树和分段树的概括,但我对这三个数据结构的实现是不同的.这个假设是真的吗？为什么？

是否可以有效地计算数轴上与单个点重叠的线段的数量P？

所有线段都位于一条数轴上（它是一个1-D世界，而不是一个3-D世界）。

每条线段都有一个起始坐标X1和一个结束坐标X2。

例子：

Line segment A spans from X1==1 to X2==3
Line segment B spans from X1==2 to X2==4
Line segment C spans from X1==3 to X2==5
Line segment D spans from X1==1 to X2==4
----------------------------------------
Ex1: Line segments that overlap point P==2: A,B and D   >>> overlap count==3.
Ex2: Line segments that overlap point P==7: None        >>> overlap count==0.
Ex3: Line segments that overlap point P==3: A,B,C and …

我有一组配对数字，需要有效地找到包含给定值的一组数字。

给定以下数字对的表示

public class Line
{
    public double Start { get; set; } //is always < end
    public double End { get; set; }
}

集合Lines可以直观地布局如下（黑线）

垂直的红线是交集标准（只是一个简单的数字，如 10.123）

我正在寻找一种有效的算法，基于搜索执行频率大于向Line集合添加的频率的假设，该算法仅返回与红色相交的黑线。（显然假设集合很大）

到目前为止我的不太理想的解决方案是

1. 将创建的行插入两个排序列表中。一个按 排序Start，另一个按 排序End
2. 在起始有序列表上进行二分搜索，查找起始大于交集条件的第一行的索引。（理论上，包括该索引及其之后的所有线都是不相交的）
3. 对最终有序列表重复 (2) 中类似的逻辑
4. 比较索引并选择剩余迭代次数最少的列表进行解析
5. 手动迭代所选列表的其余部分以查找交集

我正在寻找guava TreeRangeMap,它似乎非常适合我对项目的需求.java文档说它基于(java标准？)TreeMap,它具有get(put和next)的O(log(n))时间.

但TreeRangeMap应该是某种范围树实现,根据这个SO问题,查询的O(k + log(n))时间复杂度为O(n)空间,k为范围大小？有人可以证实这一点吗？

我对TreeRangeMap.subRangeMap()操作的时间复杂性也很感兴趣.它是否具有相同的O(k + log(n))？

谢谢.