JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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 ?
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)]
RSS