Структура данных для карты по интервалам

Пусть $n$ будет целым числом, и пусть $\mathbb{Z}$ обозначает множество всех целых чисел. Обозначим через $[a,b]$ интервал целых чисел $\{a,a+1,a+2,\dots,b\}$ .

Ищу структуру данных для представления отображения $f:[1,n] \to \mathbb{Z}$ . Я хочу, чтобы структура данных поддерживала следующие операции:

• $\text{get}(i)$ должен вернуть.$f(i)$

• $\text{set}([a,b],y)$ должен обновить $f$ так, чтобы $f(a)=f(a+1)=\cdots=f(b)=y$ , т. е. обновить $f$ до новой карты $f'$ такой, что $f'(i) = y$ для $i \in [a,b]$ и $f'(i) = f(i)$ Для$i \notin [a,b]$ .

• $\text{stab}(i)$ должен возвращать наибольший интервал$[a,b]$ , чтобы$i \in [a,b]$ и$f$ был постоянным на$[a,b]$ (т. е.$f(a)=f(a+1)=\cdots=f(b)$ ).

• $\text{add}([a,b],\delta)$ должен обновить$f$ до нового отображения$f'$ , чтобы$f'(i) = f(i) + \delta$ для$i \in [a,b]$ и$f'(i) = f(i)$ для$i \notin [a,b]$ .

Я хочу, чтобы каждая из этих операций была эффективной. Я хотел бы рассчитывать $O(1)$ или $O(\lg n)$ время , как эффективность, но $O(n)$ времени слишком медленно. Это нормально , если бегущие времена амортизируются работает раз. Существует ли структура данных, которая одновременно делает все эти операции эффективными?

(Я заметил, что подобный шаблон возникает в нескольких задачах программирования. Это обобщение, которое будет достаточно для решения всех этих проблем.)

Я считаю, что логарифмическое время для всех запросов достижимо. Основная идея состоит в том, чтобы использовать дерево интервалов, где каждый узел в дереве соответствует интервалу индексов. Я разработаю ключевые идеи, начав с более простой версии структуры данных (которая может поддерживать get и set, но не другие операции), а затем добавлю функции для поддержки других функций.

Простая схема (поддерживает get и set, но не add или stab)

Скажем , что интервал является плоским , если функция F постоянна на [ с , Ь ] , то есть, если F ( ) = е ( + 1 ) = ⋯ = е ( б ) .$[a,b]$$f$$[a,b]$$f(a)=f(a+1)=\cdots =f(b)$

Наша простая структура данных будет деревом интервалов. Другими словами, у нас есть двоичное дерево, где каждому узлу соответствует интервал (индексов). Мы будем хранить соответствующий интервал в каждом узле v дерева. Каждый лист будет соответствовать плоскому интервалу, и они будут расположены таким образом, чтобы считывание листьев слева направо давало нам последовательность последовательных плоских интервалов, которые не пересекаются и объединение которых равно [ 1 , n ] . Интервал для внутреннего узла будет объединением интервалов его двух дочерних узлов. Кроме того , в каждом узле листа л мы будем хранить значение V ( л $I(v)$$v$$[1,n]$$\ell$$V(\ell)$функции на интервале I ( ℓ ), соответствующем этому узлу (обратите внимание, что этот интервал плоский, поэтому f постоянна на интервале, поэтому мы просто сохраняем одно значение f в каждом листовом узле).$f$$I(\ell)$$f$$f$

Эквивалентно, вы можете представить, что мы разбиваем на плоские интервалы, а затем структура данных представляет собой двоичное дерево поиска, где ключами являются левые конечные точки этих интервалов. Листья содержат значение f в некотором диапазоне индексов, где f постоянно.$[1,n]$$f$$f$

Используйте стандартные методы, чтобы гарантировать, что бинарное дерево остается сбалансированным, т. Е. Его глубина составляет (где m подсчитывает текущее количество листьев в дереве). Конечно, m ≤ n , поэтому глубина всегда не более O ( lg n ) . Это будет полезно ниже.$O(\lg m)$$m$$m\le n$$O(\lg n)$

Теперь мы можем поддерживать операции get и set следующим образом:

• легко: мы проходим дерево, чтобы найти лист, интервал которого содержит i . Это в основном просто обход бинарного дерева поиска. Поскольку глубина составляет O ( LG N ) , время работы составляет O ( LG N ) .$\text{get}(i)$$i$$O(\lg n)$$O(\lg n)$

• сложнее. Это работает так:$\text{set}([a,b],y)$

  1. Сначала мы находим интервал листьев содержащий a ; если a 0 < a , то мы разделяем этот листовой интервал на два интервала [ a 0 , a - 1 ] и [ a , b 0 ] (таким образом превращая этот листовой узел во внутренний узел и вводя двух дочерних элементов).$[a_0,b_0]$$a$$a_0 < a$$[a_0,a-1]$$[a,b_0]$

  2. Далее мы находим интервал листьев содержащий b ; если b < b 1 , мы разделяем этот листовой интервал на два интервала [ a 1 , b ] и [ b + 1 , b 1 ] (таким образом, превращая этот листовой узел во внутренний узел и вводя двух дочерних элементов).$[a_1,b_1]$$b$$b < b_1$$[a_1,b]$$[b+1,b_1]$

  3. На этом этапе я утверждаю, что интервал может быть выражен как непересекающееся объединение O ( lg n ) интервалов, соответствующих некоторому подмножеству O ( lg n ) узлов в дереве. Итак, удалите всех потомков этих узлов (превратив их в листья) и установите значение, хранящееся в этих узлах, на y .$[a,b]$$O(\lg n)$$O(\lg n)$$y$

  4. Наконец, поскольку мы изменили форму дерева, мы выполним любые необходимые повороты, чтобы перебалансировать дерево (используя любую стандартную технику для поддержания баланса дерева).

  Поскольку эта операция включает в себя несколько простых операций на узлах (и этот набор узлов можно легко найти за O ( lg n ) времени), общее время для этой операции составляет O ( lg n ) .$O(\lg n)$$O(\lg n)$$O(\lg n)$

Это показывает, что мы можем поддерживать операции get и set за времени на одну операцию. Фактически, время выполнения может быть показано как O ( lg min ( n , s ) ) , где s - количество операций установки, выполненных до настоящего времени.$O(\lg n)$$O(\lg \min(n,s))$$s$

Добавление поддержки для добавления

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

Более точно, значение функции на входе я будет возмещен как сумма значений , хранящихся в узлах на пути от корня дерева вниз к листу которого интервал содержит I . В каждом узле V мы будем хранить значение V ( V ) ; если v 0 , v 1 , ... , v K представляют предков листа об к (включая сам лист), то значение функции при I ( об к ) будет$f(i)$$i$$i$$v$$V(v)$$v_0,v_1,\dots,v_k$$v_k$$I(v_k)$ .$V(v_0)+\dots + V(v_k)$

Операции get и set легко поддерживать с помощью варианта методов, описанных выше. В основном, при обходе дерева вниз, мы отслеживаем бегущую сумму значений, так что для каждого узел , что обход визит, мы будем знать сумму значений узлов на пути от корня до х . После того, как мы делаем это, простые корректировки реализации получения и установки описанного выше будет достаточно.$x$$x$

И теперь мы можем эффективно поддерживать . Сначала мы выражаем интервал [ a , b ] как объединение O ( lg n ) интервалов, соответствующих некоторому набору O ( lg n ) узлов в дереве (при необходимости разделяя узел на левой конечной точке и правой конечной точке), точно так же, как в шагах 1-3 операции установки. Теперь мы просто добавляем δ к значению, хранящемуся в каждом из этих O ( LG N $\text{add}([a,b],\delta)$$[a,b]$$O(\lg n)$$O(\lg n)$$\delta$$O(\lg n)$узлы. (Мы не удаляем их потомков.)

Это обеспечивает способ поддержки получения, установки и добавления за времени на операцию. Фактически, время выполнения каждой операции равно O ( lg min ( n , s ) ), где s подсчитывает количество операций над множествами плюс количество операций добавления.$O(\lg n)$$O(\lg \min(n,s))$$s$

Поддержка операции удара

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

(*) Интервал соответствующий каждому листу ℓ, является максимальным плоским интервалом.$I(\ell)$$\ell$

Здесь я говорю, что интервал является максимальным плоским интервалом, если (i) [ a , b ] плоский, и (ii) ни один интервал, содержащий [ a , b ], не является плоским (другими словами, для всех a ′ , Ь ' , удовлетворяющих 1 ≤ ' ≤ ≤ B ≤ B ' ≤ п , либо [ ' , Ь ' ] = $[a,b]$$[a,b]$$[a,b]$$a',b'$$1 \le a' \le a \le b \le b' \le n$ или [ a ′ , b ′ ] не плоские).$[a',b']=[a,b]$$[a',b']$

Это позволяет легко реализовать операцию «Укол»:

• находит лист, интервал которого содержит i , а затем возвращает этот интервал.$\text{stab}(i)$$i$

Однако теперь нам нужно изменить операции set и add для поддержки инварианта (*). Каждый раз, когда мы разбиваем лист на два, мы можем нарушать инвариант, если некоторая смежная пара листовых интервалов имеет одинаковое значение функции . К счастью, каждая операция set / add добавляет максимум 4 новых конечных интервала. Кроме того, для каждого нового интервала легко найти листовой интервал непосредственно слева и справа от него. Следовательно, мы можем сказать, был ли нарушен инвариант; если это так, то мы объединяем смежные интервалы, где f имеет одинаковое значение. К счастью, объединение двух смежных интервалов не вызывает каскадных изменений (поэтому нам не нужно проверять, могло ли слияние внести дополнительные нарушения инварианта). В целом, это включает в себя изучение $f$$f$ пары интервалов и, возможно, слияние их. Наконец, поскольку слияние меняет форму дерева, если это нарушает инварианты баланса, выполните любые необходимые повороты, чтобы сохранить баланс дерева (следуя стандартным методикам для поддержания баланса бинарных деревьев). В целом, это добавляет не более O ( lg n ) дополнительной работы к операциям set / add.$12=O(1)$$O(\lg n)$

Таким образом, эта окончательная структура данных поддерживает все четыре операции, и время выполнения каждой операции равно . Более точная оценка - время O ( lg min ( n , s ) ) на операцию, где s подсчитывает количество операций установки и добавления.$O(\lg n)$$O(\lg \min(n,s))$$s$

Прощальные мысли

Фу, это была довольно сложная схема. Надеюсь, я не допустил ошибок. Пожалуйста, внимательно проверьте мою работу, прежде чем полагаться на это решение.