Sir in the last you had said that segment tree is build in O(n) and query is done in O(log n) so total time complexity is O(nlogn) so than how is it beneficial than simple traversal which had time complexity O(n) only???
Segment Tree construction
A Binary Indexed Tree is used to store cumulative sums. You have an array a. You want to be able to retrieve the sum of the first k elements in O(logn) time, and you want to be able to add a quantity q to the i -th element in O(logn) time. Note that these two operations can be implemented with a normal array, but the time complexity will be O(n) and O(1).
A segment tree is a much more flexible data structure, you can use it to store many different things. You have an array a . You want to be able to retrieve the sum (or the maximum, or the minimum, or the greatest common divisor, or another associative function) of the elements between the l -th and the r -th in O(logn) time, and you want to be able to add (or to overwrite, or to multiply by…) a quantity q to the i -th element (or to every element between the l -th and the r -th) in O(logn) time.
Generally, segment tree is more powerful than binary index tree. You can use segment tree to do range maximum/minimum query( query the max or min element in range i…j for example).
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.