Почему запрос диапазона в дереве сегментов возвращает не более ceil (log_2 N) узлов?

Question

Если массив A [1..N] представлен с использованием дерева сегментов, имеющего наборы в каждом интервале, почему запрос диапазона [L..R] возвращает не более ceil (log_2 N) наборов (или непересекающихся интервалов) ?

Если натолкнулся на это утверждение при чтении этого ответа .

Цитировать:

Найти непересекающееся покрытие диапазона запроса, используя стандартная процедура запроса дерева сегментов. Мы получаем O (logn) непересекающихся узлов, объединение мультимножеств которых является именно мультимножеством значений в диапазоне запросов. Давайте назовем эти мультимножества s_1, ..., s_m (с m <= ceil (log_2 n)). </p>

Я пытался найти доказательство, но не смог найти его ни на одном сайте. Может кто-нибудь помочь мне доказать это?

Answer 1

Каждый узел представляет некоторую степень из 2 ^ n элементов, где n - высота узла. Дерево сегментов никогда не использует 2 соседних узла, потому что тогда, если оно может использовать двух соседей, оно будет использовать их родителя. Кроме того, поскольку диапазоны непрерывны, он никогда не будет использовать 2 узла в одном слое и некоторый узел, который находится ниже этого уровня и представляет некоторый диапазон между этими 2 узлами. Поэтому на каждом слое будет выбрано не более 2 узлов. Сегментное дерево состоит из O (log n) слоев, поэтому каждый запрос использует O (log n) узлов.

EDIT 1:

Фактическая граница ячейка (log_2 N) неверна, и вот один из примеров: На этом рисунке представлено дерево сегментов для массива длиной 8. Если мы сделаем запрос [1,6] (индексы, начинающиеся с нуля), он будет использовать 4 вершины (они черные на изображении) и 4 > ceil(log_2(8)) = 3