zarif_2002's blog

Help me to make my segment tree faster
By zarif_2002, history, 4 years ago, In English

I learned segment tree yesterday and tried to solve these following problems
399D - Painting The Wall
61E - Enemy is weak
459D - Pashmak and Parmida's problem
My solutions just barely pass the time limit.
81038127
81106193
81148972(needed faster I/O)
How can I strengthen this segment tree so that my solution fits into time limit completely.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think array is faster than vector when the constraint is large. Also, long long is unnecessary, using int instead of long long reduces the execution time.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

74662995

My submission for the first problem is just 300ms.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

From where you have learnt segment tree ?

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

    From everywhere, youtube gives theory, GFG gives some idea of code, then try questions on Codeforces.

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

    First of all, segment tree is not essential in your position. Cause it would look hard for you in the green region. I suggest learning segment tree after crossing 1500. What you need right now is to get good enough to solve implementation problems and logic building for div3 C, D and div2 C. Maybe you can learn binary search and stl. Believe me, doing segment tree are not going to be helpful right now.

    Once you are comfortable with the implementation and logic building problems, then move on for algorithms.

    And you can learn segment tree from here if you desperately want. https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/

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

    The competitive programmers handbook covers it nicely: https://cses.fi/book/book.pdf

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

Your segtree is fine, just use ios_base::sync_with_stdio(false). People should stop misleading other people that arrays are faster than vectors, most of the times they are not.

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

    I prefer vectors over arrays, however I would say that multi-dimensional arrays are better than multi-dimensional vectors, for example a 2D matrix where I do operations row-wise: arrays would have a great cache locality whereas in vector since the next row is at a different location you would have cache misses for all rows (though the difference would only be apparent when you are really trying to fit your slow algo in the TL xD).

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

      "in vector since the next row is at a different location", any sources about this?

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

        Ummm.... The only way I know to make a multi-dimensional vector is to use vector<vector<T>> vec(n, vector<T>(m)), and it is obvious that here the row vectors are all constructed seperately so each of them would have a different memory location.

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

      Fair point. I agree that when we start thinking about multidimensional arrays, things start to change. However, for 1D arrays I've never seen notable difference (at least, as long as you're preallocating the vector size instead of using push_back or emplace_back).

      However, there's also an upside to this. Address sanitizer can catch out-of-bounds errors on 2D vectors, and not on matrices (feel free to correct me if this is not the case).

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

        For 1D preallocated vectors, yes, I have never seen a difference. Infact, if we go by stackoverflow, there is no difference at all.

        You are right about Address Sanitizer not catching it, but UBSan (-fsanitize=undefined) does.

        → Reply