We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I'm having difficulty understanding this editorial, which means I may not understand the question. I don't see how an update can be done in log n time. It seems like it would be more efficient to simply update the array, not the sums in a BIT.
Consider the array with positions 1-17. Using a BIT, updating index 4 would cause updates to 8 and 16. All of 4's descendants would have this same cost. Therefore the updates would take nlog n time, not log n. Using an array, updates would take n time (n being the nodes you need to update) because you're simply updating indexes. Note that for this post, I’m not counting the cost of finding the descendants of a node.
Any thoughts?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Rooted Tree
You are viewing a single comment's thread. Return to all comments →
I'm having difficulty understanding this editorial, which means I may not understand the question. I don't see how an update can be done in log n time. It seems like it would be more efficient to simply update the array, not the sums in a BIT.
Consider the array with positions 1-17. Using a BIT, updating index 4 would cause updates to 8 and 16. All of 4's descendants would have this same cost. Therefore the updates would take nlog n time, not log n. Using an array, updates would take n time (n being the nodes you need to update) because you're simply updating indexes. Note that for this post, I’m not counting the cost of finding the descendants of a node.
Any thoughts?