How is space complexity O(NlogN)?
Segment tree quiz
It’s wrong. Space complexity is 4*n.
We are storing a vector in each node let’s say size is N. and seg tree’s size is 4N,then how space complexity is 4N.
Okay sorry, I didn’t know we are storing vector in each node.
Number of nodes - logn
Vector size - 4n
Total spac 4nlogn ie nlogn
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.
How number of nodes is logn ,Here number of nodes is size of segment tree and size of segment tree is 4*n?
Please watch basic videos of segment tree.
You can also visualize it from “why binary search has logn time?” isnt it similiar…?