In the lecture, it was said the worst case for range update is O(N), but I have a doubt, wouldn’t it be O(Nlogn) if the entire array has to be updated.
Since we reach the bottom of the tree in logN time and since we have to process each element in this case and then when we move up the tree in logN time updating each index.
Can you please help me with this?
Time complexity of range update
Bhaiya has clarified this at 1:57 in the video.
You can read about lazy propagation which is also covered in further lectures
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.