Есть ли более быстрая реализация для этой суммы диапазона Splay Tree?

Я закодировал сплайновое дерево. Узлы представлены следующим образом.

struct Node{
    Node *l;  /// The left  Node
    Node *r;  /// The right Node
    int v;    /// The Value
};

Теперь мне нужно знать сумму всех чисел в дереве в определенном диапазоне. Для этого я реализовал следующую функцию с именем summation.

void summation(Node *R, int st, int ed)
{
    if(!R) return;
    if(R->v < st){        /// should not call left side
        summation(R->r, st, ed);
    }
    else if(R->v > ed){   /// should not call right side
        summation(R->l, st, ed);
    }
    else{                /// should call both side
        ret+=R->v;
        summation(R->l, st, ed);
        summation(R->r, st, ed);
    }
    return;
}

ret это глобальный int переменная, которая инициализируется 0 перед вызовом summation функция. Два параметра st & ed определяет диапазон (включительно).

summation функция работает при сложности O(n). Кто-нибудь может предложить более быструю реализацию для этого??

Источник

2 ответа

Решение

Это реализация Splay Tree, которую я сделал некоторое время назад и протестировал на системе оценки SPOJ (написанной на C++):

https://ideone.com/aQgEpF

Эта реализация дерева поддерживает то, что вы просите O(log(n)),

Ключевой идеей здесь является использование разделения и слияния для извлечения поддерева, охватывающего диапазон. Кроме того, каждый узел содержит поле sum, который является суммой всех ключей в своем поддереве. sum поле лениво оценивается и передается только во время операции разделения (вдоль линии разделения), что позволяет не углубляться в уровни, которые не требуется вычислять.

Источник

Во-первых, как примечание, имея summation не возвращать ничего, вместо этого манипулируя глобальной переменной, вероятно, не такая уж хорошая идея. Вы, вероятно, должны рассмотреть вопрос об исключении этой глобальной переменной и сделать так, чтобы рекурсивная функция просто возвращала то, что она нашла (и чтобы вызов суммировал значения, возвращаемые ее дальнейшими рекурсивными вызовами, перед возвратом самой этой суммы).

Что касается вашего конкретного вопроса, вы можете оптимизировать операцию суммирования, увеличивая метаданные узла. Это уменьшит порядок роста операции суммирования, не влияя на порядок роста других операций. С другой стороны, это несколько снизит скорость других операций. Вам решать, подходит ли этот компромисс для вас.

Основная идея заключается в следующем:

  1. Оставьте внутри каждого узла другое поле, в котором указывается сумма элементов в дереве, укорененных в этом узле.

  2. Подумав немного, вы сможете увидеть, как эффективно обновлять эту информацию при обновлении дерева.

  3. С некоторыми дальнейшими размышлениями вы можете увидеть, как вы можете ответить на запрос диапазона, используя эти метаданные.

Источник
Другие вопросы по тегам