Tuesday, June 1, 2010

Array Increment Problem

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