Структура данных для обновления интервалов и запроса количества нулей

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

$\text{increase}(a,b)$ , которое увеличивает . $t[a],t[a+1],\ldots,t[b]$
$\text{decrease}(a,b)$ , которое уменьшает $t[a],t[a+1],\ldots,t[b]$ .
$\text{support}()$ , который возвращает количество индексов $i$ таких что $t[i]\neq 0$ .

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

Четырехъядерное дерево будет иметь размер , поэтому оно не является решением. Деревья Фенвика или Интервала имеют правильный вкус, но я не вижу, как их расширить, чтобы поддержать описанные выше операции. $\Theta(n^2)$

ds.data-structures cg.comp-geom Кристоф Дюрр
источник

Деревья Фенвика не будут использовать обещание, что «каждый призыв к уменьшению может быть сопоставлен с предыдущим вызовом для увеличения с теми же параметрами a, b», так что может быть более простое решение, использующее это обещание (но пока оно ускользает от меня).

Джереми

Поскольку количество вводимых вами данных не может превышать

(вы можете обнаруживать повторы и не вставлять их в структуру данных), мы по-прежнему получаем производительность

используя общую структуру данных дерева мер. См. Cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… слайд 47-52.

n^{2}

$n^2$

O (\log n)

$O(\log n)$

Чао Сюй

Джереми и Чао Сюй. Спасибо за ваши комментарии. Теперь я понимаю, как можно использовать дерево интервалов для поддержания общей длины объединения изменяющегося набора интервалов. На самом деле это очень симпатичная структура данных.

Кристоф Дюрр

Для общей проблемы структуры данных поиск по времени

требует пространства

где

- размер списка активных пар координат. Но действительно для алгоритма строчной линии

поэтому пространство остается линейным. Проблема все еще открыта для структуры данных с лучшим пространством, чем

, когда

\log (n^{2}) \in O (\log (n))

$\log(n^2)\in O(\log(n))$

O (p) \subset O (n^{2})

$O(p)\subset O(n^2)$

p

$p$

p \in O (n)

$p\in O(n)$

O (p)

$O(p)$

p \in ω (n)

$p\in\omega(n)$

Джереми

Вот хорошая ссылка, где вы можете протестировать свои реализации с другими решениями той же проблемы: spoj.com/OI/problems/NKMARS

Segal-Halevi

Ответы:

Используйте дерево сегментов - рекурсивное разбиение диапазона на меньшие диапазоны. Каждый интервал ваших операций обновления может быть разбит на диапазонов в этом рекурсивном разделе. Для каждого диапазона store: $[1,n]$ $[a,b]$ $O(\log n)$ $[x,y]$

Число интервалов , которые были увеличены и не уменьшены, так что является одним из диапазонов, на которые разбивается $c(x,y)$ $[a,b]$ $[x,y]$ $[a,b]$
Число ячеек, которые не покрыты разделенными подмножествами интервалов, которые в или ниже в рекурсии $u(x,y)$ $[x,y]$

Тогда, если рекурсивно разбито на и мы имеем $[x,y]$ $[x,z]$ $[z+1,w]$

U (Икс, Y) знак равно {\begin{cases} 0 & если с (Икс, Y) > 0 \\ U (Икс, Z) + U (Z + 1, Y) & в противном случае \end{cases}

$u(x,y)=\begin{cases} 0&\text{if }c(x,y)>0\\ u(x,z)+u(z+1,y)&\text{otherwise} \end{cases}$ поэтому мы можем обновлять каждое значение

в постоянное время, когда изменяются другие данные для диапазона. На каждый запрос поддержки можно ответить, посмотрев на

u (x, y)

$u(x,y)$

u (1, n)

$u(1,n)$

Чтобы выполнить операцию увеличения , разбейте на диапазоны , увеличьте для каждого из этих диапазонов и используйте приведенную выше формулу для пересчета для каждого из этих диапазонов и каждого из их предков. Операция уменьшения аналогична уменьшению вместо увеличения. $(a,b)$ $[a,b]$ $O(\log n)$ $c(x,y)$ $u(x,y)$

Дэвид Эппштейн
источник

[x, y]

$[x,y]$

[x, y]

$[x,y]$

[x, y]

$[x,y]$

u (x, y) = 0

$u(x,y) = 0$

[x, y]

$[x,y]$

[x, y]

$[x,y]$

[x, y]

$[x,y]$

Не могли бы вы привести пример?

Jbapple

Предположим, ваш интервал - числа [1,8]. Он рекурсивно делится на [1,4], [4,8], затем [1,2], [3,4], [5,6] и [7,8], а затем все одноэлементные диапазоны. Первоначально все раскрыто, все c [x, y] = 0, и у каждого диапазона есть u = его длина. Но затем предположим, что вы выполняете операцию увеличения [2,6]. Максимальные диапазоны O (log n), на которые можно разложить [2,6]: [2,2], [3,4] и [5,6], поэтому для этих трех мы устанавливаем c [x, y] колеблется до 1. Согласно формуле в моем ответе, это приводит к тому, что u [x, y] для этих трех диапазонов также становится равным 0. u [1,2] становится 1, u [1,4] также становится 1, u [ 5,8] = 2, а u [1,8] = 1 + 2 = 3

Дэвид Эппштейн

$\text{increase}$ $\text{decrease}$ $O(\sqrt{n}\log n)$ $\text{support}$ $O(1)$ $\Theta(\sqrt{n})$ $\text{increase}$ $\text{decrease}$ $O(\sqrt{n})$ $a$ $b$ $\omega(\log n)$

jbapple
источник

O (\sqrt{n})

$O(\sqrt{n})$

O (\log n)

$O(\log{n})$