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.
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.
Thankyou Thankyou Thankyou, I can't believe I missed this!
also, if you do really want to speed up segment tree, you can get rid of pointers and use arrays — it will work faster
fucking amateurs
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