我正在寻找一种数据结构，它可以在具有以下属性的封闭区间内有效运行：
动态添加或删除间隔
为每个间隔设置并随时更改一个数字（“深度”）。没有两个深度是相同的
查找与任何给定间隔重叠的所有间隔，按“深度”排序
我找到的最接近的结构是区间树，但它以任意顺序列出了找到的区间，相对于它们的深度。我可以收集报告的所有“未排序”间隔，然后对它们进行排序，但我希望可以避免对每个查询的结果进行排序。
请问，有没有人知道这种数据结构或有任何建议（如果可能的话）来增强间隔树以支持这种排序？
例子：
编辑
我对快速添加/删除和查询更感兴趣，而不是更新深度。如果这有助于加速其他操作，则深度可能需要 O(n)。
让我们假设您想要的算法存在。然后让我们创建一组一百万个区间，每个区间为[1, 1]，具有随机深度，并将它们插入到这样的区间树中。然后让我们查询区间[1, 1]。它应该以排序顺序返回所有间隔，复杂度为O(M + log N), 但是N = 1，因此我们M在线性时间内对一组元素进行排序。
换句话说，从区间树中获取元素后按深度排序元素在复杂性方面与理论上可能的一样好。
The depth as you set it, is equivalent to the position of intervals in their imaginary list. So, the usual list of pairs of numbers is enough. List can easily add, remove or switch its items.
If you will need also to find the depth for the given interval, make a function for it (you didn't mention the need, though)
这是我在Java中使用基本上是二叉树的TreeMap的解决方案
测试：http: //ideone.com/f0OlHI
复杂
Insert : 2 * O(log n)
Remove : 2 * O(log n)
Search : 1 * O(log n)
ChangeDepth : 7 * O(log n)
findOverlap : O(n)
间隔数据集.java
class IntervalDataSet
{
private TreeMap<Integer,Interval> map;
public IntervalDataSet ()
{
map = new TreeMap<Integer,Interval> ();
}
public void print ()
{
for(Map.Entry<Integer,Interval> entry : map.entrySet())
{
Integer key = entry.getKey();
Interval value = entry.getValue();
System.out.println(key+" => ["+value.min+","+value.max+"] ");
}
}
public boolean changeDepth (int depth, int newDepth)
{
if (!map.containsKey(depth)) return false;
if (map.containsKey(newDepth)) return false;
Interval in = map.get(depth);
in.depth = newDepth;
remove(depth); insert(in);
return true;
}
public boolean insert (Interval in)
{
if (in == null) return false;
if (map.containsKey(in.depth)) return false;
map.put(in.depth, in); return true;
}
public boolean remove (int depth)
{
if (!map.containsKey(depth)) return false;
map.remove(depth); return true;
}
public Interval get (int depth)
{
return map.get(depth);
}
public void print (int depth)
{
if (!map.containsKey(depth))
System.out.println(depth+" => X ");
else
map.get(depth).print();
}
public void printOverlappingIntervals (Interval in)
{
for (Interval interval : map.values())
if (interval.intersect(in))
interval.print();
}
public ArrayList<Interval> getOverlappingIntervals (Interval in)
{
ArrayList<Interval> list = new ArrayList<Interval>();
for (Interval interval : map.values())
if (interval.intersect(in))
list.add(interval);
return list;
}
public int size ()
{
return map.size();
}
}
间隔.java
class Interval
{
public int min;
public int max;
public int depth;
public Interval (int min, int max, int depth)
{
this.min = min;
this.max = max;
this.depth = depth;
}
public boolean intersect (Interval b)
{
return (b != null
&& ((this.min >= b.min && this.min <= b.max)
|| (this.max >= b.min && this.max <= b.max))
);
}
public void print ()
{
System.out.println(depth+" => ["+min+","+max+"] ");
}
}
测试.java
class Test
{
public static void main(String[] args)
{
System.out.println("Test Start!");
System.out.println("--------------");
IntervalDataSet data = new IntervalDataSet ();
data.insert(new Interval( 1,3, 0 ));
data.insert(new Interval( 2,4, 1 ));
data.insert(new Interval( 3,5, 3 ));
data.insert(new Interval( 4,6, 4 ));
System.out.println("initial values");
data.print();
System.out.println("--------------");
System.out.println("Intervals overlapping [2,3]");
data.printOverlappingIntervals(new Interval( 2,3, -1 ));
System.out.println("--------------");
System.out.println("change depth 0 to 2");
data.changeDepth( 0, 2 );
data.print();
System.out.println("--------------");
System.out.println("remove depth 4");
data.remove( 4 );
data.print();
System.out.println("--------------");
System.out.println("change depth 1 to 4");
data.changeDepth( 1, 4 );
data.print();
System.out.println("--------------");
System.out.println("Test End!");
}
}
间隔数据集2
复杂
initialization : O(n)
findOverlap : 2 * O(log n) + T(merge)
class IntervalDataSet2
{
private Integer [] key;
private TreeMap<Integer,Interval> [] val;
private int min, max, size;
public IntervalDataSet2 (Collection<Interval> init)
{
TreeMap<Integer,TreeMap<Integer,Interval>> map
= new TreeSet<Integer,TreeMap<Integer,Interval>> ();
for (Interval in : init)
{
if (!map.containsKey(in.min))
map.put(in.min,
new TreeMap<Integer,Interval> ());
map.get(in.min).put(in.depth,in);
if (!map.containsKey(in.max))
map.put(in.max,
new TreeMap<Integer,Interval> ());
map.get(in.max).put(in.depth,in);
}
key = new Integer [map.size()];
val = new TreeMap<Integer,Interval> [map.size()];
int i = 0;
for (Integer value : map.keySet())
{
key [i] = value;
val [i] = map.get(value);
i++ ;
}
this.size = map.size();
this.min = key [0];
this.max = key [size-1];
}
private int binarySearch (int value, int a, int b)
{
if (a == b)
return a;
if (key[(a+b)/2] == value)
return ((a+b)/2);
if (key[(a+b)/2] < value)
return binarySearch(value, ((a+b)/2)+1, b);
else
return binarySearch(value, (a, (a+b)/2)-1);
}
public TreeMap<Integer,Interval> findOverlap (Interval in)
{
TreeMap<Integer,Interval> solution
= new TreeMap<Integer,Interval> ();
int alpha = in.min;
int beta = in.max;
if (alpha > this.max || beta < this.min)
return solution;
int i = binarySearch(alpha, 0,(size-1));
int j = binarySearch(beta, 0,(size-1));
while (alpha <= beta && key[i] < alpha) i++;
while (alpha <= beta && key[j] > beta) j--;
for (int k = i; k <= j; k++)
solution.addAll ( val[k] );
return solution;
}
}
到最后想这个问题是相当困难的。你所拥有的实际上是一个一维空间，实际上是一条线。通过添加深度，您可以获得第二个坐标。通过要求深度是唯一的，您可以实际绘制图片。
您的查询是将图片的每个间隔（线）与从 x1 到 x2 的矩形以及 Y 中的每个 y 相交。
所以天真的看这个问题就是按照y的顺序比较每条线是否相交。由于您想要所有结果，因此需要 O(n) 才能找到答案。而且这个答案也必须按 O(m log m) 中的深度排序。
您尝试使用一维 R-tree。允许您在旅途中定义区域。在这样的结构中，每个节点都跨越一个从 min 到 max 的区域。您现在可以进一步拆分该区域。由于拆分实际上是拆分它，因此两个部分中都有适合的间隔，因此它们存储在节点内（而不是子节点内）。在这些子节点中，您会再次获得这样的列表，依此类推。
对于您的搜索，您检查与搜索间隔相交的所有节点和子节点。
在每个节点内，间隔列表根据它们的深度值进行排序。
因此，问题被简化为许多排序列表（可能包含在您的搜索间隔内的所有间隔）。现在必须针对与您的搜索间隔真正相交的每个间隔过滤这些列表。但是您不需要全部过滤。因为如果这样的节点区间完全包含在您的搜索区间内，则所有它的区间及其所有子区间都与您的搜索区间真正相交（因为它们完全包含在其中）。
要组合所有这些列表，您只需使用联合组合，您可以在其中选择具有最小深度的联合的下一个元素。您按其第一个元素的深度（每个列表中深度最小的元素）对所有这些列表进行排序。现在您查找第一个元素并将其移动到结果中。您现在将列表中的下一个元素与下一个列表的第一个元素进行比较，如果深度仍然更小，则将其复制到。如果深度变大，您只需使用正确的位置对它进行排序，获取 log k（其中 k 是您的集合中非空列表的数量）并继续现在的第一个列表并重复它，直到所有列表都为空或完成因为您维护每个列表的光标位置。
这样，您只需对列表进行排序并将其与下一个元素进行比较（如果它仍然更小或插入它）。
这是我能想到的最好的结构。首先，您可以轻松排除几乎所有不能与之相交的区间。比你根据潜力列表组成结果，你知道列表是完整结果的一部分（有人可以争辩说，只有一定数量的间隔列表必须检查，因为树分裂得非常快）。通过控制拆分策略，您可以控制每个部分的成本。例如，如果您仅以 >10 个间隔拆分，您将确保 k
最坏的情况很糟糕，但我想预期的实际性能会很好，而且 O(n + m log m) 会更好，因为您使用了已经排序的不同的潜在交叉点列表。
请记住，如果一个节点有子元素，它本身包含一个与分割点相交的所有区间的列表。因此，如果您的搜索区间也与分割点相交，则该节点的每个区间也是您的结果的一部分。
因此，请随意尝试这种结构。它应该很容易在一天内实施。