c# - 数轴的 C# 实现

Question

NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);

line.CheckRange(10, 25);

NumberLine 是一个代表数轴的类。我想在上面标记不同的数字范围。 CheckRange 方法应该返回 10-25 中哪些部分是我标记的，哪些是我没有标记的。在这种情况下，它应该返回 10-20 未标记，而 20-25 已标记。

我怎样才能有效地实现它，而不会做 o(n)？

谢谢。

注意:这不是作业。我需要这个用于我的自定义数据库实现事务。我正在独自学习编程。

Answer 1

解决方案很简单:将所有突出显示的值添加到 AVL或 Red-black树。我的意思是，当您执行 AddRange(1,3) 时，将整数值 1,2 和 3 插入树中。

检查范围时，只需查找端点值即可。这需要 O(log n)，这比 O(n) 快得多。

注意:插入和删除都需要O(log n)。