java - 如何确定位置 Z 是否在起点 X 和终点 Y 的区域内

Question

我有一个 JTextArea，用户可以在其中使用特殊语法创建区域。我正在寻找以最佳方式(使用线性时间算法最有效)确定当前位置是否在非重叠区域之一内的帮助。

假设我有以下内容来确定用户定义的区域(我在开始时使用正则表达式扫描文档来确定区域):

REGION START = 0, END = 20
REGION START = 21, END = 24
REGION START = 34, END = 40

我不关心用户在哪个区域，我只需要确定他们是在给定位置 X 的区域内还是区域外。我可以将区域存储为数组并循环遍历条目，直到找到一个匹配的，但这不是线性时间，如果它不匹配一个区域将花费更长的时间。

是否有更简单的方法来使用算法或以特定方式存储数据？

Answer 1

实际上你提出的算法确实是线性的。这是另一个，有点复杂，但速度更快:

• 您需要使用累积表数据结构，例如二叉索引树 (BIT)。 BIT 允许您以对数复杂度实现以下操作:
  • 更新 lo, hi, val:在索引 [lo, hi] 处添加值 val
  • 查询x:返回索引x处的和
• 对于每个区域 [lo, hi]，调用 Update(lo, hi, 1)，将 1 加到 BIT 中的适当位置
• 对于每个查询，只需检查 Query(x) 是否为零。如果是，则 x, 不与区域重叠

关于二叉索引树:http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

还有一些代码:

public class BIT {

  // AddAtPosition: adds at binary indexed tree [bit] the value [v]
  // exactly at position [i]. The binary indexed tree has size [size]

  public static void AddAtPosition(int [] bit, int size, int i, int v) {
    while(i < size) {
      bit[i] += v;
      i += (i & -i);
    }
  }

  // AddAtInterval: adds at binary indexed tree [bit] the value [v]
  // to all position from [lo] to [hi]. The binary indexed tree has size [size]

  public static void AddAtInterval(int [] bit, int size, int lo, int hi, int v) {
    AddAtPosition(bit, size, lo+1, v);
    AddAtPosition(bit, size, hi+2, -v);
  }

  // QueryAtPosition: returns the value of index [i] at binary indexed tree [bit]

  public static int QueryAtPosition(int [] bit, int i) {
    int ans = 0;
    i++;
    while(i > 0) {
      ans += bit[i];
      i -= (i & -i);
    }
    return ans;
  }

  public static void main(String [] args) {
    int [] bit = new int[10+1]; // for values from 0-9
    AddAtInterval(bit, 11, 0, 5, 1);
    AddAtInterval(bit, 11, 4, 7, 1);
    for(int i=0; i<=9; ++i) {
      System.out.print("Query At position " + i + ": ");
      System.out.println(QueryAtPosition(bit, i));
    }
  }
}