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)

• \$f(1,3) = 6\$

• \$f(2,5) = 14\$

• \$f(4,5) = 9\$

• \$f(3,5) = 12\$

• \$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 = i

-
Binary Indexed Tree is a suitable data structure for this question. However, you have to be careful of how you want to use it. For me, I would use it for storing values of "Functions".

-
Based on the code you posted here, it is difficult to tell if you modularized it properly. However, since you said it works for small input, then I believe that you have coded correctly. Try to add comments to each helper function, so others can easily follow the logic.

-
Add cases where input values exceed the maximum value or are below the minimum value specified in the original question under restriction section. Checking extreme cases is really important.

-
As you said yourself, the naming of the codes is poor. Try to use more meaningful name, i.e. in this problem, I would name "Function" as F, or "BIT_XXX" for each helper function that involves BIT implementation. Also, try to separate the main operations with helper functions (and add lots of comments).

Good luck!!

StackExchange Code Review Q#70081, answer score: 3