Range Sum of BST

Q: Какова временная сложность задачи «Сумма диапазона в BST»?

Обход с отсечением посещает узлы k в диапазоне, а также узлы максимум на двух путях от корня: время O(h + k) для дерева глубины h и O(n) , если все значения входят в диапазон. Стек или рекурсия занимают O(h) памяти.

Q: Можно ли решить задачу «Сумма диапазона в BST» с помощью симметричного обхода?

Да. Обход в порядке возрастания перечисляет значения по возрастанию, поэтому добавляй значения, начиная с low , и остановись на первом значении, которое больше high . Ранняя остановка экономит работу в правой части дерева, а отсечение — с обеих сторон.

Q: Стоит ли использовать рекурсию или стек для решения задачи «Сумма диапазона в BST»?

Оба варианта работают. Здесь глубина не превышает 14, поэтому рекурсия остаётся неглубокой. Явный стек позволяет избежать ограничения на рекурсию для высокого дерева с тысячами уровней.

ЛегкоДвоичное дерево поиска Обход деревьев

+10

Двоичное дерево поиска хранится в массиве tree в порядке уровней: корень находится по индексу 0, потомки узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), а -1 обозначает пустое место. В двоичном дереве поиска каждое значение в левом поддереве узла меньше значения этого узла, а каждое значение в его правом поддереве больше.

Верните сумму значений всех узлов v, для которых low ≤ v ≤ high, или 0, если таких узлов нет.

Функция

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: двоичное дерево поиска в порядке уровней, где -1 обозначает пустое место
lowinteger: минимальное значение для подсчёта
highinteger: наибольшее значение, до которого нужно считать
Возвращаетinteger: сумма значений узлов между low и high, включая их

Ограничения

1 ≤ tree.length ≤ 32767
Каждый tree[i] — это -1 или значение, для которого 0 ≤ tree[i] ≤ 10⁵.
tree[0] никогда не равно -1, поэтому в дереве есть как минимум один узел.
После последнего узла в массиве могут находиться дополнительные элементы -1.
Оба потомка пустого места тоже пусты, а глубина не превышает 14.
Дерево является корректным двоичным деревом поиска, поэтому все его значения различны.
0 ≤ low ≤ high ≤ 10⁵
Ответ помещается в 32-битное знаковое целое число.

Примеры

Ввод: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Вывод: 88
Пояснение: Значения от 9 до 31 — это 10, 12, 15, 20 и 31, в сумме они дают 88. 3, 8 и 40 не входят в этот диапазон.

Ввод: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Вывод: 0
Пояснение: В дереве хранятся 25, 50 и 75, и ни одно из этих значений не находится между 60 и 70, поэтому сумма равна 0. Четыре значения -1 обозначают пустые места для дочерних узлов у 25 и 75.

Ввод: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Вывод: 4
Пояснение: Когда и low, и high равны 4, учитывается только узел со значением 4. 4 с индексом 4 — это правый потомок 2, поэтому ответ — 4.

Дополнительный вопрос

Если бы тебе пришлось отвечать на тысячи разных запросов (low, high) для одного и того же дерева, как можно было бы отвечать на каждый из них за время O(log n)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Обойти все узлы и сложить значения, попадающие в диапазон, — правильно. Порядок в дереве поиска позволяет сделать меньше: значение узла подсказывает, с какой стороны находятся меньшие и большие значения, поэтому поддерево, в котором не может быть значений из диапазона, не посещается.

Посетите каждый узел

Идея

Дочерний узел существует, только если его индекс находится внутри массива и значение в этой позиции не равно -1. В первом примере у значения 12 с индексом 4 есть значения 10 и 15 с индексами 9 и 10, а у значения 31 с индексом 2 левая позиция с индексом 5 пуста.

Каждое значение из диапазона находится в каком-либо узле, поэтому обход с помощью стека, который посещает каждый узел и складывает значения, удовлетворяющие условию low ≤ v ≤ high, получает правильную сумму. Он не учитывает порядок в дереве поиска, поэтому обходит все n узлов, даже если в диапазоне всего несколько значений.

Алгоритм

Поместите корневой индекс 0 в стек и задайте total = 0.
Извлеките индекс i. Если low ≤ tree[i] ≤ high, добавьте tree[i] к total.
Поместите 2*i+1 и 2*i+2 в стек, если они находятся в пределах массива и не равны -1.
Когда стек опустеет, верните total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Обрезайте в порядке дерева поиска

Идея

Левое поддерево узла со значением v содержит только значения, меньшие v. Если v ≤ low, ни одно из них не входит в диапазон, поэтому пропусти это поддерево. Если v ≥ high, правое поддерево содержит только значения, превышающие high, поэтому пропусти его. В первом примере 31 равно high, поэтому его правый потомок 40 никогда не добавляется в стек. Значение 8 меньше low, поэтому его левый потомок 3 пропускается, а правый потомок 12 посещается, потому что значения между 8 и 20 могут входить в диапазон.

Ты посещаешь k значений в диапазоне и узлы не более чем на двух путях от корня: время O(h + k) для глубины h. Даже когда диапазон охватывает всё дерево, сложность остаётся O(n).

Алгоритм

Поместите индекс корня 0 в стек и задайте total = 0.
Извлеките индекс i и прочитайте v = tree[i]. Если low ≤ v ≤ high, добавьте v к total.
Если v > low, поместите левого потомка 2*i+1 в стек, если он существует.
Если v < high, поместите правого потомка 2*i+2 в стек, если он существует.
Когда стек опустеет, верните total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Ловушки и крайние случаи

Использование строгих сравнений. Учитываются оба конца диапазона, поэтому в третьем примере, где low = high = 4, нужно учитывать 4.
Преждевременное отсечение на один шаг. При v = low левое поддерево можно отбросить, но при v = low + 1 в нём может находиться само значение low.
Отбрасывание обеих сторон узла, находящегося вне диапазона. Значение 8 в первом примере меньше low, однако в его правом поддереве находятся 10, 12 и 15.
Чтение дочернего элемента за пределами массива. Перед чтением проверьте 2*i+1 < tree.length и считайте -1 обозначением отсутствующего дочернего элемента.
В Lua и R массивы начинаются с 1: оставляйте индексы узлов нумеруемыми с 0 для вычислений 2*i+1 и читайте tree[i + 1].

Частые вопросы3

Какова временная сложность задачи «Сумма диапазона в BST»?

Обход с отсечением посещает узлы k в диапазоне, а также узлы максимум на двух путях от корня: время O(h + k) для дерева глубины h и O(n), если все значения входят в диапазон. Стек или рекурсия занимают O(h) памяти.

Можно ли решить задачу «Сумма диапазона в BST» с помощью симметричного обхода?

Да. Обход в порядке возрастания перечисляет значения по возрастанию, поэтому добавляй значения, начиная с low, и остановись на первом значении, которое больше high. Ранняя остановка экономит работу в правой части дерева, а отсечение — с обеих сторон.

Стоит ли использовать рекурсию или стек для решения задачи «Сумма диапазона в BST»?

Оба варианта работают. Здесь глубина не превышает 14, поэтому рекурсия остаётся неглубокой. Явный стек позволяет избежать ограничения на рекурсию для высокого дерева с тысячами уровней.

def rangeSumBST(tree, low, high):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Ожидаемый вывод