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?

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