Estructura de datos para actualizaciones en intervalos y número de ceros de consulta

Estoy buscando una estructura de datos que mantenga una tabla entera de tamaño , y que permita las siguientes operaciones en el tiempo . $t$ $n$ $O(\log n)$

$\text{increase}(a,b)$ , que aumenta . $t[a],t[a+1],\ldots,t[b]$
$\text{decrease}(a,b)$ , que disminuye . $t[a],t[a+1],\ldots,t[b]$
$\text{support}()$ , que devuelve el número de índices tal que . $i$ $t[i]\neq 0$

Tiene la promesa de que cada llamada a disminuir puede coincidir con una llamada anterior para aumentar con los mismos parámetros . La aplicación que tengo en mente es un algoritmo de línea de barrido para calcular en el tiempo el área de la unión de n rectángulos rectilíneos dados. $a,b$ $O(n\log n)$

Un árbol cuádruple tendría un tamaño , por lo que no es una solución. Los árboles Fenwick o Interval tienen el sabor correcto, pero no veo cómo extenderlos para apoyar las operaciones anteriores. $\Theta(n^2)$

ds.data-structures cg.comp-geom Christoph Dürr
fuente

Los árboles de Fenwick no usarían la promesa de que "cada llamada a disminuir puede coincidir con una llamada anterior para aumentar con los mismos parámetros a, b", por lo que podría haber una solución más simple usando esa promesa (pero se me escapa por ahora).

Jeremy

Dado que el número de entrada que puede tener es como máximo (puede detectar repeticiones y no insertar en la estructura de datos), todavía obtenemos el rendimiento utilizando la estructura de datos de árbol de medida común. Ver cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… diapositiva 47-52.

n^{2}

$n^2$

O (\log n)

$O(\log n)$

Chao Xu

Jérémie y Chao Xu. Gracias por sus comentarios Ahora entiendo cómo se puede usar el árbol de intervalos para mantener la longitud total de la unión de un conjunto cambiante de intervalos. De hecho, esta es una estructura de datos muy linda.

Christoph Dürr

Para el problema general de la estructura de datos, la búsqueda en tiempo requiere espacio donde es el tamaño de la lista de pares activos de coordenadas. Pero, de hecho, para el algoritmo de línea de barrido el espacio se mantiene lineal. El problema aún está abierto para una estructura de datos con mejor espacio que , cuando .

\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)$

Jeremy

Aquí hay un buen enlace donde puede probar sus implementaciones contra otras soluciones al mismo problema: spoj.com/OI/problems/NKMARS

Erel Segal-Halevi

Respuestas:

Use un árbol de segmentos: una partición recursiva del rango en rangos más pequeños. Cada intervalo de sus operaciones de actualización puede dividirse en de los rangos en esta partición recursiva. Para cada rango almacenar: $[1,n]$ $[a,b]$ $O(\log n)$ $[x,y]$

El número de los intervalos que se han aumentado y no disminuido de tal manera que es uno de los rangos en la que se repartió $c(x,y)$ $[a,b]$ $[x,y]$ $[a,b]$
El número de celdas que no están cubiertas por subconjuntos particionados de intervalos que están en o menos en la recursividad $u(x,y)$ $[x,y]$

Entonces, si se divide recursivamente en y tenemos para que podamos actualizar cada valor de en tiempo constante cuando los otros datos para Un rango cambia. Cada consulta de soporte puede responderse mirando . $[x,y]$ $[x,z]$ $[z+1,w]$

u (x, y) = {\begin{cases} 0 & if c (x, y) > 0 \\ u (x, z) + u (z + 1, y) & otherwise \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)$

Para realizar una operación de aumento , particione en rangos , incremente para cada uno de estos rangos y use la fórmula anterior para recalcular para cada uno de estos rangos y cada uno de sus antepasados. La operación de disminución es la misma con una disminución en lugar de un incremento. $(a,b)$ $[a,b]$ $O(\log n)$ $c(x,y)$ $u(x,y)$

David Eppstein
fuente

No creo entender tu segunda bala. En el subárbol con pudrición etiquetada , ¿qué celdas no están cubiertas por subconjuntos de intervalos particionados en ? ¿No está cubierto todo el rango , entonces ?

[x, y]

$[x,y]$

[x, y]

$[x,y]$

[x, y]

$[x,y]$

u (x, y) = 0

$u(x,y) = 0$

jbapple

Depende de qué operaciones de aumento haya realizado. Inicialmente, todos están descubiertos, pero cuando aumenta un pequeño intervalo dentro de (o cualquier intervalo que comienza o termina dentro de , o que incluye en su partición) disminuye.

[x, y]

$[x,y]$

[x, y]

$[x,y]$

[x, y]

$[x,y]$

David Eppstein

¿Podrías dar un ejemplo?

jbapple

Suponga que su intervalo son los números [1,8]. Se divide recursivamente en [1,4], [4,8], luego [1,2], [3,4], [5,6] y [7,8], luego todos los rangos de un elemento. Inicialmente, todo está descubierto, todo c [x, y] = 0, y cada rango tiene u = su longitud. Pero entonces, suponga que realiza una operación de aumento [2,6]. Los rangos máximos de O (log n) en los que [2,6] se pueden descomponer son [2,2], [3,4] y [5,6], por lo que establecemos c [x, y] para esos tres varía a 1. De acuerdo con la fórmula en mi respuesta, esto hace que u [x, y] para estos tres rangos también se convierta en 0. u [1,2] se convierte en 1, u [1,4] también se convierte en 1, u [ 5,8] = 2, y u [1,8] = 1 + 2 = 3

David Eppstein

Puede admitir y en y en tiempo . $\text{increase}$ $\text{decrease}$ $O(\sqrt{n}\log n)$ $\text{support}$ $O(1)$ La idea clave es dividir la tabla en grupos de tamaño . Luego de cada operación de modificación ( o ) opera en al mayoría de grupos, y solamente los que están cerca del final de su rango ( y , en su formulación) tome tiempo. $\Theta(\sqrt{n})$ $\text{increase}$ $\text{decrease}$ $O(\sqrt{n})$ $a$ $b$ $\omega(\log n)$

jbapple
fuente

O (\sqrt{n})

$O(\sqrt{n})$

O (\log n)

$O(\log{n})$