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

13

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(Journaln) .

  • augmenter(une,b) , ce qui augmentet[a],t[a+1],,t[b] .
  • , qui diminue t [ a ] , t [ a + 1 ] , , t [ b ] .decrease(a,b)t[a],t[a+1],,t[b]
  • , qui renvoie le nombre d'indices i tels que t [ i ] 0 .support()it[i]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 O ( n log n ) l'aire de l'union de n rectangles rectilignes donnés.a,bO(nlogn)

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.Θ(n2)

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 O ( log n ) en utilisant la structure de données de l'arbre de mesure commun. Voir cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… diapo 47-52. n2O(logn)
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 ( p ) O ( n 2 )p est la taille de la liste des paires de coordonnées actives. Mais en effet pour l'algorithme sweepline p O ( n ) donc l'espace reste linéaire. Le problème est toujours ouvert pour une structure de données avec un meilleur espace que O ( p ) , lorsque plog(n2)O(log(n))O(p)O(n2)ppO(n)O(p) . pω(n)
Jeremy
2
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:

2

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

  • Le nombre d'intervalles [ a , b ] qui ont été augmentés et non diminués de telle sorte que [ x , y ] est l'une des plages dans lesquelles [ a , b ] 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 à [ x , y ] ou moins dans la récursivitéu(x,y)[x,y]

Alors si est récursivement divisé en [ x , z ] et [ z + 1 , w ] nous avons u ( x , y ) = { 0 si  c ( x , y ) > 0 u ( x , z ) + u ( z + 1 , y ) sinon[x,y][x,z][z+1,w]

u(x,y)={0if c(x,y)>0u(x,z)+u(z+1,y)otherwise
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 ( 1 , n ) .u(x,y)u(1,n)

Pour effectuer une opération d'augmentation , partitionnez [ a , b ] en plages O ( log n ) , incrémentez c ( x , y ) pour chacune de ces plages et utilisez la formule ci-dessus pour recalculer u ( x , y ) 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(logn)c(x,y)u(x,y)

David Eppstein
la source
[x,y][x,y][x,y]u(x,y)=0
[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
0

increasedecreaseO(nlogn)supportO(1)Θ(n)increasedecreaseO(n)abω(logn)

jbapple
la source
Pourquoi ne pas prendre cette approche à la limite. Au lieu de se regrouper dansO(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(Journaln)pour toutes les opérations.
S.Pek