# Binary index tree optimization

I have written code for a binary index tree. My problem is that there are many functions based on the binary index tree the function stores the sum of element within a given range of binary index tree. My task is to compute the sum of all the functions with provide range.

This example will clarify:

My array elements: A = 1 2 3 4 5

The function $f(x,y)$ is the sum of all elements of array between index $x$ and $y$ (inclusive)

1. $f(1,3) = 6$
2. $f(2,5) = 14$
3. $f(4,5) = 9$
4. $f(3,5) = 12$
5. $f(1,2) = 3$

For a given query of the form sum(a,b), I have to compute the sum of all the function from a to b.

sum(1,4) is the sum of the function from 1 to 4:

$f(1,3) + f(2,5) + f(4,5) + f(3,5) = 6+14+9+12 = 41$

The above data structure must also support for updating in the array.

• update(a,b) replaces the element stored in index a of the array with b
• update(3,7) will cause my new array to be A = 1 2 7 4 5

For any further clarification you can refer to this link.

My code is working for smaller range of input. How can I tune it to work for larger inputs?

def initupdate(x, y, n, lst):
while x <= n:
lst[x] += y
x += (x & -x)

def update(x, y, n, lst):
a = lst[x]
initupdate(x, -a, n, lst)
initupdate(x, y, n, lst)

def sumk(k, lst):
res = 0
while k:
res += lst[k]
k -= (k & -k)
return res

def sumfunc(k, nfunc, lst):
res = 0
a, b = nfunc[k]
res += sumk(b, lst)
res -= sumk(a - 1, lst)
return res

def sumfuncxy(x,y, nfunc, lst):
res=0
for k in range(x,y+1):
res+=sumfunc(k,nfunc,lst)
return res

n = int(input())
array = [0] + list(map(int, input().split()))
number = [ 0 for i in range(n + 1)]

for i in range(1, n + 1):
initupdate(i, array[i], n, number)

nfunction = [[0, 0] for i in range(n + 1)]

for i in range(1, n + 1):
lst = input().split()
lst = list(map(int, lst))
nfunction[i] = lst

q = int(input())

for i in range(q):
lst = list(map(int, input().split()))
if lst[0] == 1:
'update'
update(lst[1], lst[2], n, number)
else:
print(sumfuncxy(lst[1], lst[2], nfunction, number))


I know my naming of the variable is poor.

1. Is the choice of data structure (binary index tree) good for the problem?
2. Have I properly modularized my code?
3. Are there any vulnerability in my code?
4. Are there any further suggestions for cleaning the code?
• Welcome to Code Review! As per your description of the problem, you mentioned that your code does not work for larger inputs. As Code Review is for working code, you may want to ask at Stack Overflow instead. Please clarify if you meant that your code is too slow for larger inputs. Thanks! – wei2912 Nov 17 '14 at 11:51
• Is the problem just a performance problem for larger datasets, or does it produce the wrong result? – rolfl Nov 17 '14 at 13:16
• @wei2912 the program works correctly but my code is slow for large input.I want your suggestion and what all bluder I have made on the design and code part so that in future while writing code I bear those mistaskes in my mind. – akashchandrakar Nov 17 '14 at 13:37
• @aksam Alright, you're on-topic then. I will take a look at your code. – wei2912 Nov 17 '14 at 15:32
• (update(3,7) is an unfortunate example, as 3 is the (1-based) index of the value 3.) In update, use initupdate(x, y-a, n, lst). – greybeard Sep 24 '16 at 7:52