marius135's blog

Segment tree or binary indexed tree for binary array ?
By marius135, 10 years ago, In English

I am interested in knowing if there is a data structure that can offer better than O(log n) average complexity and offers the following 2 operations:

Increment x-> V[x] = 1 (all elements are initially 0) Query (1->y) all query are 1 based...

I know I will have O(n) increases and O(n) queries and want better than O(n log n) total time...

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the "query" operation doing — summing, checking if anything in the range is a set bit, or something else entirely?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Summing. For checking if anything in the range has a set bit, one could use rmq and obtain a theoretical O(n) for preprocessing and O(1) query.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You would need RMQ with updates for that. Can it be implemented in linear time?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        probably not, I have a few things different though... 1) I know my values are 0 and 1 only 2) I know i have at most n queries and n modifications and I want a total of under O(n log n) so it can be amortized O(n) or even O(n log logn ) 3) All my queries are 1->y which usually does not help... 4) I know the operations from the beginning

        → Reply