Rechercher un tableau pour les entiers dans une plage spécifique

Si je lis cela correctement, il y a des requêtes N-1 avec seulement C Modification, Dans ce cas, pourquoi ne résolvez pas les requêtes en arrière? Prenez d'abord la dernière requête car il implique le dernier élément de vérification de la matrice si l'élément tombe Between a et b si cela stocke le résultat dans un tableau ANS [N-1] = N-1 d'autre permet de mettre des ans [n-1] = -1, pour toute requête suivante j à partir de N-2 à 0 xxx

Tout cela peut être effectué dans O (n).

J'ai modifié la technique de Mason Bryant sur quelque chose qui fonctionne. Les problèmes étaient plus des bugs dans Findlowestindex et un bogue plus important à la recherche de l'arborescence (il peut renvoyer plusieurs résultats).

Malgré cela, cela ne résout pas le problème. O (N Journal N) Code> La configuration de l'heure est suffisamment facile, mais en utilisant cette technique, je ne peux obtenir que O ((log n) ^ 2) code> temps de requête. Je me demande si vous avez un lien avec le problème initial au cas où il y a des éclaircissements plus nombreux? Ou je me demande si le problème est vraiment satisfait. Ou peut-être o ((log n) ^ 2) code> est "à propos de" o (journal n) code> comme demande de problème, c'est inférieur à o (n) Quoi qu'il en soit. p>

La technique consiste à stocker notre réseau dans un arbre de segment typique, mais avec les informations de segment habituelles, nous stockons également, dans l'ordre, tous les index des éléments sous chaque nœud. Ce stockage supplémentaire ne prend qu'un O (n journal n) code> heure / espace Si vous l'ajoutez correctement (n éléments stockés à chacun des niveaux de log n), donc cela ne fait pas mal de notre temps de configuration. de quelque manière que ce soit qui compte. Ensuite, nous interrogeons l'arborescence pour trouver l'ensemble minimum de nœuds contenus par notre gamme de (A, B). Cette requête prend à peu près au même moment qu'une requête d'arborescence de segment typique ( O (log n) code>) et trouve au maximum environ 2 * log n segments correspondants. Comme nous interrogeons, nous trouvons l'indice le plus bas de chaque segment correspondant qui correspond à notre contrainte c. Nous pouvons utiliser une recherche binaire pour trouver cet index depuis que nous avons conservé les indices dans l'ordre, il faut donc O (journal n) code> le pire des cas pour chaque nœud correspondant. Lorsque nous l'ajoutons de manière appropriée, le temps total est o ((log n) ^ 2) code>. P>

laissez-moi savoir quelle étape vous voulez savoir si vous souhaitez clarifier. P >

C # Code: P>

void Test() {
  DateTime start;
  TimeSpan at = new TimeSpan(), bt = new TimeSpan();

  Random rg = new Random();
  for(int i = 0; i < 20; i++) {
    // build arrays from 5 to 10000 elements long, random values between 0 and 100
    // Break even time for queries is around 10000 elements in array for the values and queries used
    int[] array = (from n in Enumerable.Range(1, rg.Next(5, 10000)) select rg.Next(0, 100)).ToArray<int>();

    // Setup should be O(n log n) time/space
    ArraySearcher Searcher = new ArraySearcher(array);

    // Test each array a number of times equal to its length, with random values for a, b, c
    for(int j = 0; j < array.Length; j++) {
      int a = rg.Next(-1, 101), b = rg.Next(a, 102), c = rg.Next(0, array.Length);
      start = DateTime.Now;
      int expected = BruteSearch(array, a, b, c);
      at += DateTime.Now - start;
      // Search should be O(log n) time, but in reality is O((log n)^2) :(
      start = DateTime.Now;
      int got = Searcher.QuickSearch(a, b, c);
      bt += DateTime.Now - start;
      System.Diagnostics.Debug.Assert(got == expected);
    }
  }
  MessageBox.Show(at.ToString() + ", " + bt.ToString());
}

int BruteSearch(int[] array, int a, int b, int c) {
  for(int i = c; i < array.Length; i++)
    if(a < array[i] && array[i] < b)
      return i;
  return -1;
}

class ArraySearcher {

  SegmentNode Root;
  List<SegmentNode> Nodes;

  public ArraySearcher(int[] array) {
    Nodes = array.Select((value, index) => new SegmentNode(value, value, new List<int> { index }, null, null)).ToList<SegmentNode>();
    // Sorting will take us O(n log n)
    Nodes.Sort();
    // Creating a normal segment tree takes O(n log n)
    // In addition, in this tree each node stores all the indices below it in order
    // There are a total of n of these indices at each tree level, kept in order as we go at no extra time cost
    // There are log n levels to the tree
    // So O(n log n) extra time and space is spent making our lists, which doesn't hurt our big O notation compared to just sorting
    this.Root = SegmentNode.Merge(Nodes, 0, Nodes.Count - 1);
  }

  public int QuickSearch(int a, int b, int c) {
    return this.Root.FindLowestIndex(a, b, c);
  }

  class SegmentNode : IComparable {

    public int Min, Max;
    public List<int> Indices;
    public SegmentNode Left, Right;

    public SegmentNode(int Min, int Max, List<int> Indices, SegmentNode Left, SegmentNode Right) {
      this.Min = Min;
      this.Max = Max;
      this.Indices = Indices;
      this.Left = Left;
      this.Right = Right;
    }

    int IComparable.CompareTo(object other) {
      return this.Min - ((SegmentNode)other).Min;
    }

    public static SegmentNode Merge(List<SegmentNode> Nodes, int Start, int End) {
      int Count = End - Start;
      if(Start == End)
        return Nodes[Start];
      if(End - Start == 1)
        return SegmentNode.Merge(Nodes[Start], Nodes[End]);
      return SegmentNode.Merge(SegmentNode.Merge(Nodes, Start, Start + Count/2), SegmentNode.Merge(Nodes, Start + Count/2 + 1, End));
    }

    public static SegmentNode Merge(SegmentNode Left, SegmentNode Right) {
      int LeftCounter = 0, RightCounter = 0;
      List<int> NewIndices = new List<int>();
      while(LeftCounter < Left.Indices.Count || RightCounter < Right.Indices.Count) {
        if(LeftCounter < Left.Indices.Count && (RightCounter == Right.Indices.Count || Left.Indices[LeftCounter] < Right.Indices[RightCounter]))
          NewIndices.Add(Left.Indices[LeftCounter++]);
        else
          NewIndices.Add(Right.Indices[RightCounter++]);
      }
      return new SegmentNode(Left.Min, Right.Max, NewIndices, Left, Right);
    }

    public int FindLowestIndex(int SeekMin, int SeekMax, int c) {
      // This will find at most O(log n) matching segments, always less than 2 from each level of the tree
      // Each matching segment is binary searched in at worst O(log n) time
      // Total does indeed add up to O((log n)^2) if you do it right
      if(SeekMin < this.Min && SeekMax > this.Max)
        return FindLowestIndex(this.Indices, c);
      if(SeekMax <= this.Min || SeekMin >= this.Max)
        return -1;
      int LeftMatch = this.Left.FindLowestIndex(SeekMin, SeekMax, c);
      int RightMatch = this.Right.FindLowestIndex(SeekMin, SeekMax, c);
      if(LeftMatch == -1)
        return RightMatch;
      if(RightMatch == -1)
        return LeftMatch;
      return LeftMatch < RightMatch ? LeftMatch : RightMatch;
    }

    int FindLowestIndex(List<int> Indices, int c) {
      int left = 0, right = Indices.Count - 1, mid = left + (right - left) / 2;
      while(left <= right) {
        if(Indices[mid] == c)
          return c;
        if(Indices[mid] > c)
          right = mid - 1;
        else
          left = mid + 1;
        mid = left + (right - left) / 2;
      }
      if(mid >= Indices.Count)
        return -1;
      // no exact match, so return the next highest.
      return Indices[mid];
    }
  }
}