Binary index tree optimization

Question

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?

• wei2912: 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!
• rolfl: Is the problem just a performance problem for larger datasets, or does it produce the wrong result?
• अज्ञ: @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.
• wei2912: @aksam Alright, you're on-topic then. I will take a look at your code.
• greybeard: (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).

Answer 1

1. 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".

2. 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.

3. 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.

4. 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!!