Why is my segment tree so slow?

Revision en1, by SAT2020, 2022-07-20 19:23:12

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SAT2020 2022-07-20 19:23:12 778 Initial revision (published)