Requêtes de sous-réseau

Alors j'essayais de résoudre ce problème de programmation.Requêtes de sous-réseau

Étant donné un tableau de nombres et quelques requêtes. Chaque requête vous donne trois nombres a, b, c et vous demande de répondre à la somme de tous les éléments de l'index a à l'index b (tous deux inclus) qui sont inférieurs ou égaux à c.

par exemple:

tableau donné: {2,4,6,1,5,1,6,4,5,4}

3 requêtes doivent être traitées:

2 4 4 -> 5 ans = ie {4 + 1}

1 5 3 -> 3 ans = ie {2 + 1}

4 5 1 -> 1 ans =

chaque valeur dans le tableau est inférieure à 10^5, la longueur du tableau et le nombre de requêtes pourrait aller jusqu'à 10^5

Voici ce que j'ai fait J'ai utilisé l'algorithme de Mo (décomposition de racine carrée) pour trier les requêtes, et créé un arbre indexé binaire pour stocker la somme cumulative des éléments moins que toutes les valeurs de 1-10^5, et a fait une mise à jour en passant des requêtes aux requêtes. Avec cet algorithme, la complexité globale de ma solution est O (q * sqrt (N) * log (N)) mais elle n'est pas assez rapide. Je cherchais un meilleur algorithme. Je pense que la décomposition de la racine carrée des requêtes ne fonctionnerait pas. Existe-t-il un meilleur algorithme pour résoudre ce problème?

Je me demandais si une structure de données pouvait résoudre ce problème dont je ne suis pas au courant?

Source

2017-06-06 ash

Vous voulez dire "a", "b", "c" sont des index? Et utilisez-vous l'indexation basée sur zéro? – Bahrom

@Bahrom a et b sont des indices basés sur '1', c est un nombre. – ash

Vous pouvez le décomposer dans l'autre sens. A savoir, construire un arbre de demi-réseaux (c'est (n log n) espace). Triez chaque sous-tableau et construisez un tableau de somme cumulatif pour celui-ci. Maintenant, vos requêtes sont (log n) chacun (log n pour identifier les sous-réseaux et un autre journal n pour trouver la somme cumulée dans chaque sous-tableau).

Par exemple, si votre tableau d'origine

  5,10,2,7,16,4,8,9

vous devez d'abord construire cet arbre

  5,10,2,7,16,4,8,9 
      /  \ 
     5,10,2,7   16,4,8,9 
    / \   / \ 
    5,10  2,7  16,4  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9

les trier puis tout

  2,4,5,7,8,9,10,16 
      /  \ 
     2,5,7,10   4,8,9,16 
    / \   / \ 
    5,10  2,7  4,16  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9

Maintenant, si vous voulez répondre à dire requête (1,6,8) (les index sont basés sur 0) vous décomposer l'intervalle (1,6) en sous-intervalles binaires (1) (2,3) (4,5) (6) (il y a de plus de 2 log n puis de trouver la réponse pour chacun séparément (0 pour (1) = {10}, 9 pour (2,3) = {2,7}, 4 pour (4,5) = {16,4}, 8 pour (6) = {8}) et résumez-les.

bâtiment arbre initial peut être fait dans (n log n) si vous triez paires (valeur, index) une fois, puis passer un peu plus le journal n fois de tableau trié (une fois pour chaque niveau de l'arbre) et copie les valeurs à leurs nœuds respectifs.

Source

2017-06-07 06:35:51

Concernant l'implémentation, vous pouvez définir une fonction récursive sur l'arbre qui (1) retourne juste la somme du nœud courant s'il est entièrement contenu dans l'intervalle, (2) retourne le résultat de la fonction sur l'enfant de gauche ou de droite somme si l'intervalle est seulement sur le côté gauche ou droit, (3) renvoie la somme de l'appel de fonction sur les enfants gauche et droit si l'intervalle est des deux côtés, c'est-à-dire dépasse le milieu. Cela semble plus simple que d'essayer de diviser complètement l'intervalle au début. Cela semble juste O (log n) par requête. – Dukeling

Pouvez-vous élaborer sur la façon dont vous trouvez la somme réelle des éléments inférieure ou égale à c (en O (log n))? Une façon de le faire serait de stocker une somme cumulative pour chaque nœud, puis de faire une recherche binaire dans ce nœud pour trouver la somme applicable. – Dukeling

@Dukeling oui c'est exactement ce que j'avais en tête –

Requêtes de sous-réseau

Répondre

Questions connexes