
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(x1) 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(x1) for x in xrange(10)]
print [sum(x) for x in xrange(10)]
print [bit[x] for x in xrange(10)]
