grimalk's blog

Task on array
By grimalk, history, 9 years ago, In English

Given array V of integers.

Need to answer query of two types:

  1. Given L, R, A, B, need to count how many A ≤ j ≤ B are so that L ≤ Vj ≤ R

  2. Given i and X, Vi = X

Someone told me that this is impossible task in O(log n).

Is this true? Can anyone prove me that or prove it being wrong?

It seems to be complicated. If anyone has any idea how to solve it faster than O(log2 n) I'd also like to hear that. O(log n * log max) is also pretty obvious solution (max is maximum value that can be stored in array)

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution in O(log2 n) is pretty simple with segment tree + treap, but there is no obvious way to speed it up to O(log n)

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

Hmmm why should it be impossible if you know the number of integers more than R and less than L then u can find it
this can be done offline with O(qlgn) and online with persistent segment tree with the same complexity
maybe i didn't understand the problem

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Ok that is nice solution without updates. What if we have them? My bad that I didn't mention them in first place.

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

    Can you please explain how to do it with persistent segment tree? What do we store in every version of segment tree ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      This can be solved with persistent dynamic segment tree (Which will work in O(log max)) or with persistent treap which will work in O(log n)

      I don't really know if we can use simple segment tree there.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        We are solving offline task, so we can compress all numbers and any number will be in [1;n]. After this we can solve it with simple segment tree

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

You can get O(log) per query if there are no update operations. With online update operations best you can get is O(log^2)

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

    Yeah, probably persistent tree still can save us there. Can you tell me something about why is log2 best that i can get with updates?

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

      Think about storing all the corresponding elements of the original array in every segment tree node.

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

        To be honest I didn't get your answer. Can you elaborate?

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

          Make a segment tree where each node contains a treap the numbers from the range it determines. Now for answering a query for something like how many numbers in your treap are bigger than L and smaller than R you can use the structure of the treap with an additional value in each node — the size of the subtree. The query is similar to using treaps for range queries in an array.

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

            Not that.

            I know log2 solution on my own, I mean is there any way to prove that there can't exist a structure that works in O(log n)

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

              Proving a theoretical best complexity is actually very difficult. I'd be surprised if someone actually proved that this problem has no O(log n) per query solution. It is just that no one knows such one.

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

This may be useful. Maybe.

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

    I guess that's unfortunately not what I'm looking for. Most of these weird structures (range-tree / exponential tree) are based on that they have around O(n log n) time to build themselves and can answer queries fast after that. If we have updates like in this task we can't rebuild structure all the time. So I believe that query Vi = X can't be fast with this kind of data structures.

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

Intuitive reasoning of why you wouldn't be able to get down to O(log):

You can imagine each element as point with coordinates (i, Vi). It is easy to see then that the questions asked are just "How many points are there in this rectangle". Since this is a problem in 2-dimensional space, updating and answering online is intuitively gonna take O(log2) time, as 2D structure is required.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Not every 2D task is calculated in O(log2) I'm not so experienced in these, but task like "is there any point in such borders: (x ≤ A, L ≤ y ≤ R) where A, L, R are in a query" is solvable in O(log). It's not like I have seen other 2D tasks these would be solvable in O(log) though.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Could you explain O(log) solution of the problem you proposed, assuming we can update (that is, add and remove points) and have to answer online?

      Note that if the answer of your query is F(A, L, R) then finding the answer to the problem given in this blog would be simply F(B, L, R) - F(A - 1, L, R)

      P.S.

      After your clarification on PM I understand that your problem is decision problem, that is you want to know only whether there is such point and not counting them. In this case yea — you can get down to O(log), but decision problems are usually easier to solve, as I said, my explanation is intuitive, not a valid mathematical proof :)

      → Reply