Дан массив V целых чисел.
Нужно обрабатывать следующие два типа запросов
Запрос содержит L, R, A, B, требуется посчитать, сколько таких j, что A ≤ j ≤ B и L ≤ Vj ≤ R
Запрос содержит i и X, $V_i = $
Один человек сказал мне, что это невозможно решить с асимптотикой O(log n) на запрос.
Правда ли это? Будет неплохо увидеть доказательство того, что это правда или решение, если это утверждение неверно.
(Также мне были интересны другие асимптотики, которые могут быть лучше чем O(log2 n).) Решение за O(log n * log max) тоже вполне очевидное решение (max — максимальное число, которое может быть в массиве V)
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)
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
Ok that is nice solution without updates. What if we have them? My bad that I didn't mention them in first place.
Can you please explain how to do it with persistent segment tree? What do we store in every version of segment tree ?
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.
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
Yeah, I guess you are right.
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)
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?
Think about storing all the corresponding elements of the original array in every segment tree node.
To be honest I didn't get your answer. Can you elaborate?
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.
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)
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.
This may be useful. Maybe.
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.
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.
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.
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 :)