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 indexa
of the array withb
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.
- Is the choice of data structure (binary index tree) good for the problem?
- Have I properly modularized my code?
- Are there any vulnerability in my code?
- Are there any further suggestions for cleaning the code?
update(3,7)
is an unfortunate example, as 3 is the (1-based) index of the value 3.) Inupdate
, useinitupdate(x, y-a, n, lst)
. \$\endgroup\$