Блог пользователя ricardogg

Deleting lines from LiChao tree
Автор ricardogg, история, 5 лет назад, По-английски

Recently I read about LiChao Tree for convex hull trick, however I couldn't find any resource on internet showing on how to perform delete operations on LiChao trees. Is it even possible to do delete operations on such segment tree?

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Deleting from Li Chao tree can be done using this technique.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry about commenting so late here, but how can we store the changes to the LiChao tree, do we need to keep all logN values of the path from the root to the leaf in the tree?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Just make the LiChao persistent, it should be as easy as any persistent structure, and then do the DynaCon D&C trick to support deletes. Note that this only support deleting in an offline way, i don't think its possible in less than sqrt(N) per query for online

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

You can do it online using SQRT with rebuilding. Maintaing bins with size at most K, everytime you insert some line, try to insert in some open bin or open a new bin, for each bin, keep the CHT of the lines in the bin as well. For a query operation, just pass for each N/K bins and keep the min/max of querys in the CHTs of the bins. For a delete operation, find the bin that the line is, erase the line and rebuild the entire bin.

You can choose K that minimize O(N/K * log(N)) + O(K)

→ Ответить