JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Binary Indexed Trees Quick question:
 Re: Quick question: (response to post by assaf.sela) | Reply Let's say we have an array of 10 elements:(actual) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10](sum) [1, 3, 6, 10, 15, 21, 28, 36, 45, 55](BIT) [1, 3, 3, 10, 5, 11, 7, 36, 9, 19]Now we change the '3' into an '8':(actual) [1, 2, 8, 4, 5, 6, 7, 8, 9, 10](sum) [1, 3, 11, 15, 20, 26, 33, 41, 50, 60](BIT) [1, 3, 8, 15, 5, 11, 7, 41, 9, 19]With the sum array, every sum starting from the changed index had to be updated; however, only 3 values in the BIT were updated. If no values are being changed then sum arrays are normally adequate, but for dynamic data BITs take O(logN) time to update as opposed to the O(N) of sum arrays.Here's the Python session I used to generate those lists:```bit = [0 for x in xrange(10)]   def update(x, y): while x < 10: bit[x] += y x |= x+1   def sum(x): y = 0 while x >= 0: y += bit[x] x &= x+1 x -= 1 return y   for i in xrange(10): update(i, i+1)   print [sum(x) - sum(x-1) for x in xrange(10)] print [sum(x) for x in xrange(10)] print [bit[x] for x in xrange(10)]   update(2, 8 - 3)   print [sum(x) - sum(x-1) for x in xrange(10)] print [sum(x) for x in xrange(10)] print [bit[x] for x in xrange(10)] ```
 Quick question: | Reply Just to see if I get it:For the problem given, a.k.a summing over a given range, this is not a good solution, since we can do O(1) if we simply use partial sums in a temp array (sum(i,j) = partialSum(j) - partialSum(i)).Nevertheless, this structure is good when asking different questions about a range (e.g. maximum value in a given range / RMQ ).My point is - the given example (taken from topCoder) should have been chosen differently.Am I wrong ?
 Forums Tutorial Discussions Binary Indexed Trees Quick question: Previous Thread  |  Next Thread