I have been trying to get an index of sum range query for the array. Suppose that I have an array like:
{1, 3, 5, 7, 9, 11}
With a segment tree like that
{36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}
Here is an image of it.
How can I get the index for the query 0-2 in the segment tree array (for example index for the 0-2 index is 1, for 3-5 it is 2)?
import math
#get a size of list and return list of lists
#where every list is the indexes that should be on that place in the tree
def list_divid(size):
index_list = list(range(size))
out = []
out.append([index_list[:]])
divide = True
while divide:
divide = False
for i in out[-1]:
if len(i)>1:
divide = True
if not divide:
break
add_to_out = []
for i in range(len(out[-1])):
if len(out[-1][i])==1:
add_to_out.append([])
if len(out[-1][i])%2==0:
middle_index = int((len(out[-1][i]))/2)
add_to_out.append(out[-1][i][:middle_index])
add_to_out.append(out[-1][i][middle_index:])
if len(out[-1][i])%2!=0:
middle_index = math.ceil((len(out[-1][i]))/2)
add_to_out.append(out[-1][i][:middle_index])
add_to_out.append(out[-1][i][middle_index:])
out.append(add_to_out)
rv = []
for i in out:
rv+=i
return rv
#getting first and last index, and list size
#create the tree using list_divid
#then find the index of the list in the list of lists
def get_index1(first,last, list_len):
tree = list_divid(list_len)
for i in range(len(tree)):
if tree[i][0] == first and tree[i][-1] == last:
return i
I liked that question