Editing Range minimum query
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 44: | Line 44: | ||
==Dynamic== | ==Dynamic== | ||
− | The block-based solution handles the dynamic case as well; we must simply remember, whenever we update an element, to recompute the minimum element in the block it is in. This gives <math>O(\sqrt{n})</math> time per update, and, assuming a uniform random distribution of updates, the expected update time is | + | The block-based solution handles the dynamic case as well; we must simply remember, whenever we update an element, to recompute the minimum element in the block it is in. This gives <math>O(\sqrt{n})</math> time per update, and, assuming a uniform random distribution of updates, the expected update time is constant. This is because if we decrease an element, we need only check whether the new value is less than the current minimum (constant time), whereas if we increase an element, we only need to recompute the minimum if the element updated was the minimum before (which takes <math>O(\sqrt{n})</math> time but has a probability of occurring of only <math>O(1/m) = O(1/\sqrt{n})</math>). Unfortunately, the query still has average-case time <math>O(\sqrt{n})</math>. |
The [[segment tree]] can be computed in linear time and allows both queries and updates to be answered in <math>O(\log n)</math> time. It also allows, with some cleverness, entire ranges to be updated at once (efficiently). Analysis of the average case is left as an exercise to the reader. | The [[segment tree]] can be computed in linear time and allows both queries and updates to be answered in <math>O(\log n)</math> time. It also allows, with some cleverness, entire ranges to be updated at once (efficiently). Analysis of the average case is left as an exercise to the reader. |