ЕФИКАСНО ДИЗАЈНИРАЈТЕ УМЕТАК, БРИСАЊЕ И СРЕДЊИ УПИТИ НА СЕТУ

С обзиром на празан сет у почетку и бројним упитима на њеном тренутку следеће врсте:

Уметнути - Уметните нови елемент 'Кс'. Избрисати - Избришите постојећи елемент 'Кс'. Средњи - Штампајте средњи елемент бројева који су тренутно у сету

Пример:

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

За излагачку сврху претпостављамо следеће, али ове претпоставке нису ограничења овде речи:
1. У сваком случају, сви елементи су различити, то се од њих не догађа више од једном.
2 'Медијан' упит је направљен само када у сету постоје непарни број елемената. (Морат ћемо да направимо два упита на стаблу сегмента у случају парно бројева)
3. Елементи у сету крећу се од 1 до + 10 ^ 6.

Метода 1 (наивно)
У наивном имплементацији можемо да урадимо прве две упите у О (1), али последњи упит у О (МАКС_ЕЛЕМ) где је Мак_елем максимални елемент свих времена (укључујући избрисане елементе).

Претпоставимо мало низа бројање [] (величине 10 ^ 6 + 1) да би се одржило рачунање сваког елемента у подскупини. Следе једноставне и самосталне алгоритме за 3 упита:
Убаци к упит:

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

Обриши к упит:

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

Средњи упит:

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

Илустрација броја низа [] представља сет {1 4 7 8 9} Медијан Елемент је '7':

Ефикасно дизајн Уметните Обриши и средњи упите на сет

"Средњи" упит намерава да пронађе (Н + 1) / 2. '1' у низу у овом случају 3. '1'; Сада то учинимо исто коришћењем дрвећа сегмента.

Метода 2 (користећи Сегментно дрво )
Правимо сегментно дрво Да бисте сачували збир интервала где интервал [А б] представља број елемената присутних у сету који је тренутно у опсегу [А Б]. На пример, ако узмемо у обзир горе наведени пример упит (3 7) повраћај 2 упита (4 4) враћа 1 упит (5 5) враћа 0.

Уметање и брисање упита је једноставно и обе се могу имплементирати коришћењем ажурирања функција (Инт Кс инт разл.) (Додаје 'разл' 'у индексу' к ')

Алгоритам

// 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]

Горе наведена рекурзивна функција ради у О (Дневник (мак_елем)) (У овом случају Мак_елем је 10 ^ 6) и користи се за уметање и брисање следећим позивима:

Уметање 'Кс' се врши помоћу ажурирања (1 0 10 ^ 6 к 1). Имајте на уму да је коријен стабла донесен старт индекс преноси се као 0 и крајњи индекс као 10 ^ 6 тако да се све распони који имају Кс ажурирају се.
Избриши 'Кс' се ради помоћу ажурирања (1 0 10 ^ 6 к -1). Имајте на уму да је коријен стабла донесен старт индекс преноси се као 0 и крајњи индекс као 10 ^ 6 тако да се све распони који имају Кс ажурирају се.

Сада је функција да пронађете индекс са КТХ '1' где "К 'у овом случају ће увек бити (Н + 1) / 2 Ово ће много радити као бинарна претрага коју можете сматрати рекурзивним функцијама бинарних претраживања на сегменту.

Узмимо пример да схватимо наш сет који тренутно има елементе {1 4 7 8 9} и самим тим је заступљен следећим дрветом сегмента.

Ако смо на чвори без листа, сигурни смо да има и децу да видимо да ли лево дете има више или једнаког броја нечијег "к" ако је одговор да јесте да наши индекс буде у супротном ако леви подтрет буде у супротном, сигуран смо да наши индекс налази се у правом подвоју. Ми то рекурзивно радимо да бисмо стигли на наш индекс и одатле га враћамо.

Алгоритам

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

Горе наведена рекурзивна функција ради у О (Дневник (мак_елем)) .

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>

Излаз:

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

Закључак:
Сва три упита улазе у О (Дневник (мак_елем)) У овом случају Мак_елем = 10 ^ 6 па је лог (мак_елем) приближно једнак 20.
Дрвећа сегмента користи О (мак_елем) Простор.

Ако је упит за брисање није било, проблем је могао и са познатим алгоритамом овде .