ricardogg's blog

Deleting lines from LiChao tree
By ricardogg, history, 5 years ago, In English

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?

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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)

→ Reply