Given an array A consisting of 'n' elements. Do the following both operations in O(log n) time using a data structure.
Increment (A,i,j,x) : This should increment elements from A to A[j] by value x .
Report(A,j) : This should report A[j]
Trivially in an array Increment takes O(j-i) time and report takes O(1) . Now we need to store in a data structure (can be augmented) such that both operations takes O (log n) time.
(Interesting data structure for this one http://en.wikipedia.org/wiki/Segment_tree)
No comments:
Post a Comment