noobinho's blog

Dynamic Segment Trees
By noobinho, history, 6 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do you indent your code so weirdly?

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

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?

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

    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.

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

      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()-1 as 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

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

        Wow, thank you! It was really helpful

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

          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

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

            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.net/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?

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

              On each set or get query you add new log(n) vertices, so it is O(m * log(n)), thanks for link

              → Reply