Реализация дерева сегментов в Python

Question

Я пытаюсь закодировать новые структуры данных, которые я изучаю в Python, и следующая функция является частью дерева сегментов.

def query(root,interval,xy=ref_ll([False,False])):
    print interval,root
    if root.interval == interval or point(root.interval):
        return root.quadrant.reflect(root.xy * xy) #Is always gonna be of the form [a,b,c,d]
    a = q_list([0,0,0,0])
    if interval[0] < root.r.interval[0]:
        a = query(root.l,[interval[0],min(interval[1],root.l.interval[1])],root.xy * xy)
    if interval[1] > root.l.interval[1]:
        a = query(root.r,[max(interval[0],root.r.interval[0]), interval[1]],root.xy * xy)
    return a

Я ожидаю, что это произойдет за O (h) время (h - высота дерева), но это не так, может кто-то указать на ошибку, которую я сделал. Благодарю.

РЕДАКТИРОВАТЬ Для идеи дерева сегментов, посмотрите на http://community.topcoder.com/i/education/lca/RMQ_004.gif

Условие завершения функции - если интервал имеет форму (1,1), то есть это точка, а не диапазон. Все функции реализованы. Рабочий вход: http://pastebin.com/LuisyYCY

Вот весь код. http://pastebin.com/6kgtVWAq

Answer 1

Это, вероятно, потому что вы расширяете список для каждого уровня дерева. Средняя временная сложность расширения списка составляет O (k), где k - размер списка с правой стороны. Размер списка с правой стороны равен O (h), поэтому средняя общая сложность по времени равна O (h ² ).