Реализация запроса в дереве отрезков снизу

Реализация запроса снизу вверх

Алгоритм

Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации запроса сверху вниз, итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности.

Построим дерево отрезков и установим границы отрезка на соответствующие листья. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Продолжаем до тех пор, пока границы не пересекутся.

Псевдокод

Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a [math] \circ [/math] b, а результат считаем на отрезке [left, right].

  query(left, right)
     result = neutral; // Присваиваем результату значение нейтрального элемента (например для поиска суммы надо присвоить значение 0)
     while left < right // Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
        if (left div 2) * 2 == left // Проверяем, является ли левая граница правым сыном (индексация с 0)
           result = result [math] \circ [/math] data[left]; // Если является, то пересчитаем результат и перенесем левую границу
           left = (left + 1) div 2; 
        else
           left = left div 2; // Если не является, то установим границу на родительский элемент текущей границы
        if (right div 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
           result = result [math] \circ [/math] data[right];
           right = (right - 1) div 2;
        else
           right = right div 2;
     if left == right // После окончания цикла проверяем совпали ли границы  
        result = result [math] \circ [/math] data[left]; // Если надо пересчитываем результат
     return result;