如何获取线段树查询的索引？

Question

我一直在尝试获取数组的总和范围查询的索引。假设我有一个像这样的数组：

{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}

这是它的图片。

如何在线段树数组中获取查询 0-2 的索引（例如 0-2 索引的索引为 1，3-5 为 2）？

Answer 1

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

我喜欢这个问题

如何获取线段树查询的索引？

How to get index of segment tree query?

python

algorithm

segment-tree