SUUNNITELMA, POISTA JA MEDIAANIKYSELYT TEHOKKAASTI SARJASSA

Annetaan alun perin tyhjä sarja ja useita kyselyjä jokaisessa mahdollisesti seuraavista tyypeistä:

Lisätä - Aseta uusi elementti 'x'. Poistaa - Poista olemassa oleva elementti 'x'. Mediaani - Tulosta sarjassa olevien numeroiden mediaanielementti

Esimerkki:

Input : Insert 1 Insert 4 Insert 7 Median Output : The first three queries should insert 1 4 and 7 into an empty set. The fourth query should return 4 (median of 1 4 7).

Expository -tarkoitusta varten oletamme seuraavat, mutta nämä oletukset eivät ole tässä käsiteltyä menetelmän rajoituksia:
1. Joka tapauksessa kaikki elementit ovat erillisiä, mikä ei ole mitään niistä, useammin kuin kerran.
2. "Mediaani" -kysely tehdään vain silloin, kun sarjassa on pariton määrä elementtejä. (Meidän on tehtävä kaksi kyselyä segmenttipuussa tasaisten lukujen tapauksessa)
3. SET -elementit ovat välillä 1 - +10^6.

Menetelmä 1 (naiivi)
Naiivissa toteutuksessa voimme tehdä kaksi ensimmäistä kyselyä O (1): ssä, mutta viimeinen kysely O (Max_elem), jossa max_elem on kaikkien aikojen suurin elementti (mukaan lukien poistetut elementit).

Oletetaan taulukko laskea[] (Koko 10^6 + 1) Avaruuden kunkin elementin määrän ylläpitämiseksi. Seuraavat ovat yksinkertaisia ja itsestään selittäviä algoritmeja 3 kyselyyn:
Lisää X -kysely:

 count[x]++; if (x > max_elem) max_elem = x; n++;

Poista X -kysely:

 if (count[x] > 0) count[x]--; n--;

Mediaani kysely:

 sum = 0; i = 0; while( sum  <= n / 2 ) { i++; sum += count[i]; } median = i; return median;

Kuva taulukon määrästä [], joka edustaa sarjaa {1 4 7 8 9} Mediaani -elementti on '7':

Suunnittele tehokkaasti poisto- ja mediaanikyselyt sarjaan

'Mediaani' -kysely aikoo löytää (n + 1)/2: n '1' taulukosta tässä tapauksessa 3. '1'; Nyt teemme saman segmenttipuun avulla.

Menetelmä 2 (käyttämällä Segmenttipuu -A
Teemme a segmenttipuu väliajojen summan säilyttäminen, jolloin aikaväli [A B] edustaa alueen tällä hetkellä olevien joukkojen lukumäärää [A B]. Esimerkiksi, jos tarkastellaan yllä olevaa esimerkkikyselyä (3 7) palauttaa 2 kyselyä (4 4) palauttaa 1 kysely (5 5) palauttaa 0.

Lisää ja poista kyselyt ovat yksinkertaisia ja molemmat voidaan toteuttaa käyttämällä toimintopäivitystä (int x int diff) (lisää 'diff' indeksissä 'x')

Algoritmi

// adds ‘diff’ at index ‘x’   update(node a b x diff)   // If leaf node If a == b and a == x segmentTree[node] += diff // If non-leaf node and x lies in its range If x is in [a b] // Update children recursively update(2*node a (a + b)/2 x diff) update(2*node + 1 (a + b)/2 + 1 b x diff) // Update node segmentTree[node] = segmentTree[2 * node] + segmentTree[2 * node + 1]

Yllä oleva rekursiivinen funktio toimii O (log (max_elem)) (Tässä tapauksessa Max_elem on 10^6) ja sitä käytetään sekä asettamiseen että poistoon seuraavilla puheluilla:

Lisää 'x' tehdään päivityksellä (1 0 10^6 x 1). Huomaa, että puun juuret ohitetaan Start -hakemistoa 0 ja päätyhakemisto 10^6 niin, että kaikki X: n alueet päivitetään.
Poista 'x' tehdään päivityksellä (1 0 10^6 x -1). Huomaa, että puun juuret ohitetaan Start -hakemistoa 0 ja päätyhakemisto 10^6 niin, että kaikki X: n alueet päivitetään.

Nyt funktio löytää hakemisto kth '1', jossa 'k' tässä tapauksessa on aina (n + 1) / 2, tämä toimii paljon kuin binaarihaku, voit ajatella sitä rekursiivisena binaarihakutoiminnona segmenttipuussa.

Otetaan esimerkki ymmärtääksesi, että sarjaamme on tällä hetkellä elementtejä {1 4 7 8 9}, ja siten sitä edustaa seuraava segmenttipuu.

Jos olemme ei-lehtisolmussa, olemme varmoja, että siinä on molemmat lapset, näemme, onko vasemmalla lapsella enemmän tai yhtä suurta määrää kuin 'K', jos kyllä, olemme varmoja, että hakemistomme on vasemmassa subtree-alueella, jos vasemmalla subtreellä on vähemmän määriä 1: n kanssa kuin k, olemme varmoja, että hakemistomme on oikeassa subtree. Teemme tämän rekursiivisesti saavuttaaksemme hakemistomme ja sieltä palautamme sen.

Algoritmi

1.findKth(node a b k) 2. If a != b 3. If segmentTree[ 2 * node ] >= k 4. return findKth(2*node a (a + b)/2 k) 5. else 6. return findKth(2*node + 1 (a + b)/2 + 1 b k - segmentTree[ 2 * node ]) 7. else 8. return a

Yllä oleva rekursiivinen funktio toimii O (log (max_elem)) .

C++

    // A C++ program to implement insert delete and    // median queries using segment tree    #include          #define maxn 3000005    #define max_elem 1000000    using     namespace     std  ;          // A global array to store segment tree.    // Note: Since it is global all elements are 0.    int     segmentTree  [  maxn  ];          // Update 'node' and its children in segment tree.    // Here 'node' is index in segmentTree[] 'a' and    // 'b' are starting and ending indexes of range stored    // in current node.    // 'diff' is the value to be added to value 'x'.    void     update  (  int     node       int     a       int     b       int     x       int     diff  )      {         // If current node is a leaf node       if     (  a     ==     b     &&     a     ==     x     )         {         // add 'diff' and return       segmentTree  [  node  ]     +=     diff  ;         return     ;         }             // If current node is non-leaf and 'x' is in its       // range       if     (  x     >=     a     &&     x      <=     b  )         {         // update both sub-trees left and right       update  (  node  *  2       a       (  a     +     b  )  /  2       x       diff  );         update  (  node  *  2     +     1       (  a     +     b  )  /  2     +     1       b       x       diff  );             // Finally update current node       segmentTree  [  node  ]     =     segmentTree  [  node  *  2  ]     +         segmentTree  [  node  *  2     +     1  ];         }      }          // Returns k'th node in segment tree    int     findKth  (  int     node       int     a       int     b       int     k  )      {         // non-leaf node will definitely have both       // children; left and right       if     (  a     !=     b  )         {         // If kth element lies in the left subtree       if     (  segmentTree  [  node  *  2  ]     >=     k  )         return     findKth  (  node  *  2       a       (  a     +     b  )  /  2       k  );             // If kth one lies in the right subtree       return     findKth  (  node  *  2     +     1       (  a     +     b  )  /  2     +     1           b       k     -     segmentTree  [  node  *  2  ]);         }             // if at a leaf node return the index it stores       // information about       return     (  segmentTree  [  node  ])  ?     a     :     -1  ;      }          // insert x in the set    void     insert  (  int     x  )      {         update  (  1       0       max_elem       x       1  );      }          // delete x from the set    void     delete  (  int     x  )      {         update  (  1       0       max_elem       x       -1  );      }          // returns median element of the set with odd    // cardinality only    int     median  ()      {         int     k     =     (  segmentTree  [  1  ]     +     1  )     /     2  ;         return     findKth  (  1       0       max_elem       k  );      }          // Driver code    int     main  ()      {         insert  (  1  );         insert  (  4  );         insert  (  7  );         cout      < <     'Median for the set {147} = '          < <     median  ()      < <     endl  ;         insert  (  8  );         insert  (  9  );         cout      < <     'Median for the set {14789} = '       < <     median  ()      < <     endl  ;         delete  (  1  );         delete  (  8  );         cout      < <     'Median for the set {479} = '       < <     median  ()      < <     endl  ;         return     0  ;      }

Java

    // A Java program to implement insert delete and    // median queries using segment tree    import     java.io.*  ;   class   GFG  {   public     static     int     maxn     =     3000005  ;   public     static     int     max_elem     =     1000000  ;   // A global array to store segment tree.    // Note: Since it is global all elements are 0.    public     static     int  []     segmentTree     =     new     int  [  maxn  ]  ;   // Update 'node' and its children in segment tree.    // Here 'node' is index in segmentTree[] 'a' and    // 'b' are starting and ending indexes of range stored    // in current node.    // 'diff' is the value to be added to value 'x'.    public     static     void     update  (  int     node       int     a       int     b           int     x       int     diff  )   {          // If current node is a leaf node       if     (  a     ==     b     &&     a     ==     x     )         {             // Add 'diff' and return       segmentTree  [  node  ]     +=     diff  ;         return     ;         }          // If current node is non-leaf and 'x'      // is in its range      if     (  x     >=     a     &&     x      <=     b  )      {          // Update both sub-trees left and right      update  (  node     *     2       a       (  a     +     b  )     /     2       x       diff  );      update  (  node     *     2     +     1       (  a     +     b  )     /     2     +     1        b       x       diff  );             // Finally update current node      segmentTree  [  node  ]     =     segmentTree  [  node     *     2  ]     +      segmentTree  [  node     *     2     +     1  ]  ;      }   }   // Returns k'th node in segment tree    public     static     int     findKth  (  int     node       int     a           int     b       int     k  )   {          // Non-leaf node will definitely have both       // children; left and right      if     (  a     !=     b  )      {          // If kth element lies in the left subtree       if     (  segmentTree  [  node     *     2  ]     >=     k  )      {      return     findKth  (  node     *     2       a       (  a     +     b  )     /     2       k  );      }          // If kth one lies in the right subtree      return     findKth  (  node     *     2     +     1       (  a     +     b  )     /     2     +     1        b       k     -     segmentTree  [  node     *     2  ]  );          }          // If at a leaf node return the index it stores       // information about       return     (  segmentTree  [  node  ]     !=     0  )     ?     a     :     -  1  ;   }   // Insert x in the set   public     static     void     insert  (  int     x  )   {      update  (  1       0       max_elem       x       1  );   }   // Delete x from the set    public     static     void     delete  (  int     x  )      {      update  (  1       0       max_elem       x       -  1  );      }   // Returns median element of the set   // with odd cardinality only    public     static     int     median  ()   {      int     k     =     (  segmentTree  [  1  ]     +     1  )     /     2  ;         return     findKth  (  1       0       max_elem       k  );   }   // Driver code    public     static     void     main  (  String  []     args  )   {      insert  (  1  );         insert  (  4  );         insert  (  7  );      System  .  out  .  println  (  'Median for the set {147} = '     +         median  ());      insert  (  8  );         insert  (  9  );      System  .  out  .  println  (  'Median for the set {14789} = '     +      median  ());      delete  (  1  );         delete  (  8  );         System  .  out  .  println  (  'Median for the set {479} = '     +         median  ());   }   }   // This code is contributed by avanitrachhadiya2155

Python3

    # A Python3 program to implement insert delete and   # median queries using segment tree   maxn   =   3000005   max_elem   =   1000000   # A global array to store segment tree.   # Note: Since it is global all elements are 0.   segmentTree   =   [  0   for   i   in   range  (  maxn  )]   # Update 'node' and its children in segment tree.   # Here 'node' is index in segmentTree[] 'a' and   # 'b' are starting and ending indexes of range stored   # in current node.   # 'diff' is the value to be added to value 'x'.   def   update  (  node     a     b     x     diff  ):   global   segmentTree   # If current node is a leaf node   if   (  a   ==   b   and   a   ==   x   ):   # add 'diff' and return   segmentTree  [  node  ]   +=   diff   return   # If current node is non-leaf and 'x' is in its   # range   if   (  x   >=   a   and   x    <=   b  ):   # update both sub-trees left and right   update  (  node   *   2     a     (  a   +   b  )  //  2     x     diff  )   update  (  node   *   2   +   1     (  a   +   b  )  //  2   +   1     b     x     diff  )   # Finally update current node   segmentTree  [  node  ]   =   segmentTree  [  node   *   2  ]   +   segmentTree  [  node   *   2   +   1  ]   # Returns k'th node in segment tree   def   findKth  (  node     a     b     k  ):   global   segmentTree   # non-leaf node will definitely have both   # children left and right   if   (  a   !=   b  ):   # If kth element lies in the left subtree   if   (  segmentTree  [  node   *   2  ]   >=   k  ):   return   findKth  (  node   *   2     a     (  a   +   b  )  //  2     k  )   # If kth one lies in the right subtree   return   findKth  (  node   *   2   +   1     (  a   +   b  )  //  2   +   1     b     k   -   segmentTree  [  node   *   2  ])   # if at a leaf node return the index it stores   # information about   return   a   if   (  segmentTree  [  node  ])   else   -  1   # insert x in the set   def   insert  (  x  ):   update  (  1     0     max_elem     x     1  )   # delete x from the set   def   delete  (  x  ):   update  (  1     0     max_elem     x     -  1  )   # returns median element of the set with odd   # cardinality only   def   median  ():   k   =   (  segmentTree  [  1  ]   +   1  )   //   2   return   findKth  (  1     0     max_elem     k  )   # Driver code   if   __name__   ==   '__main__'  :   insert  (  1  )   insert  (  4  )   insert  (  7  )   print  (  'Median for the set {147} ='    median  ())   insert  (  8  )   insert  (  9  )   print  (  'Median for the set {14789} ='    median  ())   delete  (  1  )   delete  (  8  )   print  (  'Median for the set {479} ='    median  ())   # This code is contributed by mohit kumar 29

    // A C# program to implement insert delete    // and median queries using segment tree    using     System  ;   class     GFG  {       public     static     int     maxn     =     3000005  ;   public     static     int     max_elem     =     1000000  ;   // A global array to store segment tree.    // Note: Since it is global all elements are 0.   public     static     int  []     segmentTree     =     new     int  [  maxn  ];   // Update 'node' and its children in segment tree.    // Here 'node' is index in segmentTree[] 'a' and    // 'b' are starting and ending indexes of range stored    // in current node.    // 'diff' is the value to be added to value 'x'.    public     static     void     update  (  int     node       int     a           int     b       int     x       int     diff  )   {          // If current node is a leaf node       if     (  a     ==     b     &&     a     ==     x  )      {          // Add 'diff' and return       segmentTree  [  node  ]     +=     diff  ;         return     ;         }          // If current node is non-leaf and 'x'      // is in its range      if     (  x     >=     a     &&     x      <=     b  )      {          // Update both sub-trees left and right      update  (  node     *     2       a       (  a     +     b  )     /     2       x       diff  );      update  (  node     *     2     +     1       (  a     +     b  )     /     2     +     1        b       x       diff  );             // Finally update current node      segmentTree  [  node  ]     =     segmentTree  [  node     *     2  ]     +      segmentTree  [  node     *     2     +     1  ];      }   }   // Returns k'th node in segment tree   public     static     int     findKth  (  int     node       int     a        int     b       int     k  )   {          // Non-leaf node will definitely have both       // children; left and right      if     (  a     !=     b  )      {          // If kth element lies in the left subtree       if     (  segmentTree  [  node     *     2  ]     >=     k  )      {      return     findKth  (  node     *     2       a           (  a     +     b  )     /     2       k  );      }          // If kth one lies in the right subtree      return     findKth  (  node     *     2     +     1       (  a     +     b  )     /     2     +     1        b       k     -     segmentTree  [  node     *     2  ]);      }          // If at a leaf node return the index it      // stores information about       if     (  segmentTree  [  node  ]     !=     0  )      {      return     a  ;      }      else      {      return     -  1  ;      }   }   // Insert x in the set   public     static     void     insert  (  int     x  )   {      update  (  1       0       max_elem       x       1  );   }   // Delete x from the set    public     static     void     delete  (  int     x  )      {      update  (  1       0       max_elem       x       -  1  );      }   // Returns median element of the set   // with odd cardinality only   public     static     int     median  ()   {      int     k     =     (  segmentTree  [  1  ]     +     1  )     /     2  ;      return     findKth  (  1       0       max_elem       k  );   }   // Driver code   static     public     void     Main  ()   {      insert  (  1  );         insert  (  4  );         insert  (  7  );      Console  .  WriteLine  (  'Median for the set {147} = '     +      median  ());      insert  (  8  );         insert  (  9  );      Console  .  WriteLine  (  'Median for the set {14789} = '     +      median  ());      delete  (  1  );         delete  (  8  );         Console  .  WriteLine  (  'Median for the set {479} = '     +      median  ());   }   }   // This code is contributed by rag2127

JavaScript

     <  script  >   // A Javascript program to implement insert delete and   // median queries using segment tree          let     maxn     =     3000005  ;      let     max_elem     =     1000000  ;          // A global array to store segment tree.      // Note: Since it is global all elements are 0.      let     segmentTree     =     new     Array  (  maxn  );      for  (  let     i  =  0  ;  i   <  maxn  ;  i  ++  )      {      segmentTree  [  i  ]  =  0  ;      }   // Update 'node' and its children in segment tree.   // Here 'node' is index in segmentTree[] 'a' and   // 'b' are starting and ending indexes of range stored   // in current node.   // 'diff' is the value to be added to value 'x'.   function     update  (  node    a    b    x    diff  )   {      // If current node is a leaf node      if     (  a     ==     b     &&     a     ==     x     )      {          // Add 'diff' and return      segmentTree  [  node  ]     +=     diff  ;      return     ;      }          // If current node is non-leaf and 'x'      // is in its range      if     (  x     >=     a     &&     x      <=     b  )      {          // Update both sub-trees left and right      update  (  node     *     2       a       Math  .  floor  ((  a     +     b  )     /     2  )     x       diff  );      update  (  node     *     2     +     1       Math  .  floor  ((  a     +     b  )     /     2  )     +     1        b       x       diff  );          // Finally update current node      segmentTree  [  node  ]     =     segmentTree  [  node     *     2  ]     +      segmentTree  [  node     *     2     +     1  ];      }   }   // Returns k'th node in segment tree   function     findKth  (  node    a    b    k  )   {      // Non-leaf node will definitely have both      // children; left and right      if     (  a     !=     b  )      {          // If kth element lies in the left subtree      if     (  segmentTree  [  node     *     2  ]     >=     k  )      {      return     findKth  (  node     *     2       a       Math  .  floor  ((  a     +     b  )     /     2  )     k  );      }          // If kth one lies in the right subtree      return     findKth  (  node     *     2     +     1       Math  .  floor  ((  a     +     b  )     /     2  )     +     1        b       k     -     segmentTree  [  node     *     2  ]);          }          // If at a leaf node return the index it stores      // information about      return     (  segmentTree  [  node  ]     !=     0  )     ?     a     :     -  1  ;   }   // Insert x in the set   function     insert  (  x  )   {      update  (  1       0       max_elem       x       1  );   }   // Delete x from the set   function     delet  (  x  )   {      update  (  1       0       max_elem       x       -  1  );   }   // Returns median element of the set   // with odd cardinality only   function     median  ()   {      let     k     =     (  segmentTree  [  1  ]     +     1  )     /     2  ;      return     findKth  (  1       0       max_elem       k  );       }   // Driver code   insert  (  1  );   insert  (  4  );   insert  (  7  );   document  .  write  (  'Median for the set {147} = '     +      median  ()  +  '  
'  );   insert  (  8  );   insert  (  9  );   document  .  write  (  'Median for the set {14789} = '     +      median  ()  +  '  
'  );   delet  (  1  );   delet  (  8  );   document  .  write  (  'Median for the set {479} = '     +      median  ()  +  '  
'  );       // This code is contributed by unknown2108    <  /script>

Lähtö:

Median for the set {147} = 4 Median for the set {14789} = 7 Median for the set {479} = 7

Päätelmä:
Kaikki kolme kyselyä juoksevat sisään O (log (max_elem)) Tässä tapauksessa max_elem = 10^6 Joten log (max_elem) on suunnilleen yhtä suuri kuin 20.
Segmenttipuu käyttää O (max_elem) tila.

Jos poistokyselyä ei ollut siellä, ongelma olisi voinut tehdä myös kuuluisan algoritmin kanssa tässä .