Problem in Max Query-1

#1

I built the segment tree ,also coded the query
everything works well but since the value of k chanes in each query i have to rebuit the tree again and again hence encountering tle
in that case what should i do
it’s better to do a linear search if i solve the question this way.

#2

Why do we need to build again??
We are using segment tree to store range answers!
We will just query every time. Build work needs to be done just once only.!
Please have a look at this short code, its easy to understand the logic and implementation.

1 Like
#3

Thanks!
I got it
correct if am wrong
so every node in the seg tree is a vector of sorted nubers for the respective ranges.
and then we do a O(log N) search to get the answer from the segment tree

only one doubt
Use of the back_inserter in merge() can’t we just use begin(tree[index])[it gives time runtime error on using it ]

#4

It only works the way it has been used in code i guess, not like how you said.
I am glad you have understood that logic very well!

#5

I feel i have resolved your doubt. You may mark the thread resolved fro your side if so :slight_smile: