I'm trying to solve the problem: http://acm.timus.ru/problem.aspx?space=1&num=1439. It consists basically in m (1 <= m <= 10^5) queries in an ordered set which can be of two types: 1) eliminate an element of the ordered set (the number of elements eliminated is at most 10^4); 2) find the kth element of the ordered set. The ordered set can have at most n elements (1 <= n <= 10^9).The elements are {1,2,...,n} at the beginning. I tryed to code a dynamic segment tree to solve in O(m*logn) of time, as follows:https://ideone.com/e.js/jLFIMv. However, it gave MLE. So, I want to know what I can do to improve the memory used. Thanks in advance
Why do you indent your code so weirdly?
At the current time your node is 32 bytes size. You can use indexes in array / vector against pointers because one pointer is 8 bytes, but one index is 4 bytes (32-8=24, 66% memory). You exactly need to keep integers l and r in node? Maybe you can put l and r as parameters in functions in "set" and "get" queries?
With the contraints that were given (1 <= n <= 10^9) I think it's infeasible to use indexes in array. I think the only way is doing the segment tree with pointers and dynamically. It would be possible to use a segment tree in an array if it was possible to do a compression in the elements of the ordered sets (an offline solution), but I can't realize how to do that.
I mean that we have a vector, that contains nodes. Root has index 0. When we add child, we do push back in end and save value
(int)tree.size()-1as index of child.UPD: Accepted with 52 MB memory
UPD 2: Accepted with 26 MB memory
As you can see, optimizations of using memory, which I said, works
Wow, thank you! It was really helpful
It was helpful for me too, because I did not know about Dynamic Segment Tree before, can you provide a list on problems which can be easy solved with this structure, maybe on coseforces?
And your solutions works in O(mlog(n)) time
I didn't know this structure before this problem. In fact, I'm doing a list that my teacher gave me and there is only this problem about dynamic segment trees there, but there is a post from three years ago in codeforces with another problems: https://codeforces.me/blog/entry/19080
Yes, I realized that my solution works in O(m*logn). I think it would work in O(m*logn²) if I used updateSegTree(query(num,Root,1,n),-1,Root); but as I did q = query(num,Root,1,n); and after updateSegTree(q,-1,Root,1,n); it works in O(m*logn). Is it correct?
On each set or get query you add new log(n) vertices, so it is O(m * log(n)), thanks for link