java - How to determine if position Z is within regions with start X and end Y -

i have jtextarea user can create regions using special syntax. looking assistance in best way (most efficient using linear time algorithm) determine if current position within 1 of non-overlapping regions.

let's assume have following determine user defined regions (i scan document @ start using regex determine regions):

region start = 0, end = 20 region start = 21, end = 24 region start = 34, end = 40 

i don't care region user in, need determine if in or out of region, given position x. store regions array , loop through entries until find 1 matches, isn't linear time , take longer if didn't match region.

is there easier way using algorithm or storing data in way?

actually algorithm proposing indeed linear. here one, bit more complicated, faster:

• you need use cumulative table data structure, binary indexed tree (bit). bit allows implement following operations logarithmic complexity:
  • update lo, hi, val: add @ indices [lo, hi] value val
  • query x: return sum @ index x
• for each region [lo, hi], call update(lo, hi, 1), adding 1 appropriate positions in bit
• for each query check if query(x) zero. if yes, x, not overlap region

about binary indexed trees: http://community.topcoder.com/tc?module=static&d1=tutorials&d2=binaryindexedtrees

and code:

public class bit {    // addatposition: adds @ binary indexed tree [bit] value [v]   // @ position [i]. 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);     }   }    // addatinterval: adds @ binary indexed tree [bit] value [v]   // position [lo] [hi]. 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 value of index [i] @ binary indexed tree [bit]    public static int queryatposition(int [] bit, int i) {     int ans = 0;     i++;     while(i > 0) {       ans += bit[i];       -= (i & -i);     }     return ans;   }    public static void main(string [] args) {     int [] bit = new int[10+1]; // values 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 @ position " + + ": ");       system.out.println(queryatposition(bit, i));     }   } }