yaksha's blog

Segment tree is very slow!
By yaksha, history, 6 years ago, In English

Hi, So this has happened before , and it happens from time to time , only this time I really got frustrated and hence am asking this question . . Why is my segment tree so slow?

Some problems like this -> 301D - Yaroslav and Divisors , have the official solution, the same as the solution that I code but somehow my segment tree is always very slow. This has happened before in live contests as well . Maybe my implementation is very bad , that's why I want to learn where I am making mistake , and please provide me with a better implementation if I am making a mistake..

My implementation to the above problem,using segment trees, which TLE's --> 36075338 . Help me out on this please!

UPDATE: I solved the problem doing some minor optimizations like scanf/printf and using int instead of long long , but my solution is still very slow compared to other solutions..

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

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Try to do not use ll while it does not need, because it doubles your calculations.

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

    Thanks for the tip , I tried that and earlier my code TLE'd on test 24 .. .

    Now it TLE's on test 35 , definitely an improvement but still lacking :(

    36076125

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

There's much faster iterative version of segment tree, refer this.

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

Did you try using scanf and printf ?

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

    I just did and it passed , but look how slow it is -->

    36076672

    Other solutions are WAY faster than this , despite the fact that I am not using long long and also using printf and scanf , my solution runs in 1400 ms while several others run in 800ms , this makes a huge difference in contests!

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

I think you should use 'long long' when you need, and if you want to speed up, use 'scanf' and 'printf' instead of 'cin' and 'cout'. Or you can read more about 'Lazy update of Segment Tree'.

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

    ofc I can do these things but that's not my point , there are other solutions out there similar to mine , no one of them uses lazy update but still run faster , ~800ms while mine runs in 1400ms , after a lot of small optmizations

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

  1. endl -> "\n"

  2. remove pragmas

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

    Sorry I dont know much about pragmas , but aren't the first few lines supposed to fasten my solution a little bit?

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

      I know that pragmas will speed up your solution if simple operations are present

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

      remove the Ofast pragma, keep the other two. Ofast has only been bad in my experience, but the processor optimizations won't be harmful, they have only ever given me speed increase or no change.

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

Auto comment: topic has been updated by yaksha (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it
  1. Don't use endl unless its an interactive problem.
  2. move the update tree[id] upwards(before recursive call) as you always know how much it will increase. This will allow tail-recursion optimization.
  3. inline your left and right functions
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

36081515

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

    okay so "\n" and cin.tie and cout.tie make so much difference! , Noted

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

Your query function may degrade into O(n) behavior. Try changing it.

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

    How exactly?

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

    can you elaborate more please?!

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

      Sure.

      Your query only terminates when l and r perfectly matches up with x and y. At worst case these will be the leaf nodes. This is O(n).

      A way to fix this is to add code which immediately terminates when your segment is completely within or completely without.

      if (l > y || r < x) return null; //some invalid value

      if (l >= x && r <= y) return tree[id];

      Hope this helps.

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

        The values before calling the query function are actually changed to fit the boundaries of the node that is being called. Read the query function again. I don't think what you've said can happen in this code.

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

          Sorry I did not make myself clear.

          I meant the modified [x,y] (as it keeps cutting down by 2) because in the worst case this will terminate when it becomes the leaf nodes and only encompass a single element. Such a query would be O(n).

          → Reply