SAT2020's blog

Why is my segment tree so slow?
By SAT2020, history, 21 month(s) ago, In English

Hey everyone,

I recently wrote my first segment tree program. While it works properly, the tree itself is extremely slow, especially in the build phase. For instance, with just a sample size of 20,000, the tree takes 3.9 seconds to build on Codeforces! I'm wondering what I can do to speed it up, or if slow build times are the natural result of using object-based trees. Also, any general tips for writing trees and increasing their speed would be greatly appreciated!

Here is my code. It takes two numbers as input: t (the number of queries) and n (the size of the dataset). Both queries and the dataset are generated randomly. Please let me know if you have any questions about how the code works.

Code: https://codeshare.io/8pBOLZ

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

»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it 
lChild = new SegTree(arr, lm, mid);
rChild = new SegTree(arr, mid+1, rm);

When vector is passed to a function, a copy of vector is created! These two lines make your program time complexity $$$O(n^{2})$$$. Pass vector by reference instead.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Thankyou Thankyou Thankyou, I can't believe I missed this!

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      also, if you do really want to speed up segment tree, you can get rid of pointers and use arrays — it will work faster

      → Reply
»
21 month(s) ago, # |
  Vote: I like it -30 Vote: I do not like it

fucking amateurs

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In fact, you can simply use arrays to store your segment tree: the left child of index i is i*2, and the right child is i*2+1

→ Reply