Search code examples
algorithmsearchdata-structuresdictionarybloom-filter

Filter for range queries on a set

We have a set S of keys.

For membership queries (is k in S?), bloom filters often help us quickly determine that a key is not in the set.

How can we filter range queries (is there a key from the range [k1,k2] in S?) ?

Solution

  • You can solve this problem in time O(log n) using either Segment Trees or Fenwick Trees.

    With segment trees, you can ask the question is there a bit-set in the range [a..b]? This question can be answered in time O(log n). Also, you can set (or unset) a single bit in time O(log n).

    Similarly with Fenwick Trees.

    Assumption: Keys k1, k2, etc... are integers - we must make this assumption so that we can make sense of the range [k1..k2].