pythonalgorithmsegment-tree

How to get index of segment tree query?


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.

visualisation

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)?


Solution

  • 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