Structure de données pour les mises à jour sur les intervalles et interrogation du nombre de zéros

Je recherche une structure de données qui maintiendrait une table entière $t$ de taille $n$ , et permettant les opérations suivantes dans le temps $O(\log n)$ .

$\text{increase}(a,b)$ , ce qui augmente $t[a],t[a+1],\ldots,t[b]$ .
, qui diminue . $\text{decrease}(a,b)$ $t[a],t[a+1],\ldots,t[b]$
, qui renvoie le nombre d'indices tels que . $\text{support}()$ $i$ $t[i]\neq 0$

Vous avez la promesse que chaque appel à diminuer peut être comparé à un appel précédent pour augmenter avec les mêmes paramètres . L'application que j'ai en tête est un algorithme sweepline pour calculer dans le temps l'aire de l'union de n rectangles rectilignes donnés. $a,b$ $O(n\log n)$

Un quadruple arbre aurait la taille , donc ce n'est pas une solution. Les arbres Fenwick ou Interval ont la bonne saveur, mais je ne vois pas comment les étendre pour prendre en charge les opérations ci-dessus. $\Theta(n^2)$

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

Les arbres de Fenwick n'utiliseraient pas la promesse que "chaque appel à diminuer peut être mis en correspondance avec un appel précédent pour augmenter avec les mêmes paramètres a, b", donc il pourrait y avoir une solution plus simple en utilisant cette promesse (mais cela m'échappe pour l'instant).

Jeremy

Étant donné que le nombre d'entrées que vous pouvez avoir est au plus

(vous pouvez détecter des répétitions et ne pas insérer dans la structure de données), nous obtenons toujours des performances

utilisant la structure de données de l'arbre de mesure commun. Voir cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… diapo 47-52.

n^{2}

$n^2$

O (\log n)

$O(\log n)$

Chao Xu

Jérémie et Chao Xu. Merci pour vos commentaires. Je comprends maintenant comment l'arbre d'intervalle peut être utilisé pour maintenir la longueur totale de l'union d'un ensemble d'intervalles changeant. Il s'agit en fait d'une très jolie infrastructure de données.

Christoph Dürr

Pour le problème général de structure des données, la recherche dans le temps

nécessite un espace

où

est la taille de la liste des paires de coordonnées actives. Mais en effet pour l'algorithme sweepline

donc l'espace reste linéaire. Le problème est toujours ouvert pour une structure de données avec un meilleur espace que

, lorsque

\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

Voici un joli lien où vous pouvez tester vos implémentations contre d'autres solutions au même problème: spoj.com/OI/problems/NKMARS

Erel Segal-Halevi

Réponses:

Utilisez une arborescence de segments - une partition récursive de la plage en plages plus petites. Chaque intervalle de vos opérations de mise à jour peut être partitionné en des plages de cette partition récursive. Pour chaque plage magasin: $[1,n]$ $[a,b]$ $O(\log n)$ $[x,y]$

Le nombre d'intervalles qui ont été augmentés et non diminués de telle sorte que est l'une des plages dans lesquelles est partitionné $c(x,y)$ $[a,b]$ $[x,y]$ $[a,b]$
Le nombre de cellules qui ne sont pas couvertes par des sous-ensembles partitionnés d'intervalles qui sont à ou moins dans la récursivité $u(x,y)$ $[x,y]$

Alors si est récursivement divisé en et nous avons $[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}$ afin que nous puissions mettre à jour chaque valeur

en temps constant lorsque les autres données d'une plage changent. Chaque requête de support peut être répondue en regardant

u (x, y)

$u(x,y)$

u (1, n)

$u(1,n)$

Pour effectuer une opération d'augmentation , partitionnez en plages , incrémentez pour chacune de ces plages et utilisez la formule ci-dessus pour recalculer pour chacune de ces plages et pour chacun de leurs ancêtres. L'opération de diminution est la même avec un décrément au lieu d'un incrément. $(a,b)$ $[a,b]$ $O(\log n)$ $c(x,y)$ $u(x,y)$

David Eppstein
la source

[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]$

Pouvez-vous donner un exemple?

jbapple

Supposons que votre intervalle soit les nombres [1,8]. Il est récursivement divisé en [1,4], [4,8], puis [1,2], [3,4], [5,6] et [7,8], puis toutes les plages à un élément. Initialement, tout est découvert, tous c [x, y] = 0, et chaque plage a u = sa longueur. Mais alors, supposons que vous effectuez une opération d'augmentation [2,6]. Les plages maximales O (log n) dans lesquelles [2,6] peut être décomposé sont [2,2], [3,4] et [5,6], donc nous fixons c [x, y] pour ces trois gammes à 1. Selon la formule dans ma réponse, cela fait u [x, y] pour ces trois gammes devenir également 0. u [1,2] devient 1, u [1,4] devient également 1, u [ 5,8] = 2, et u [1,8] = 1 + 2 = 3

David Eppstein

$\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
la source

Pourquoi ne pas prendre cette approche à la limite. Au lieu de se regrouper dans

O (\sqrt{n})

$O(\sqrt{n})$ seaux, on peut plutôt former un arbre similaire à celui-ci: 1 / \ 2 3 / \ / \ 4 5 6 7 dont, en mettant à jour, on prend

O (\log n)

$O(\log{n})$ pour toutes les opérations.

S.Pek