ricardogg's blog

By ricardogg, history, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    2 weeks 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?

    • »
      »
      »
      13 days 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

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Would you like to elaborate more on how to use persistent Li Chao tree, I have implemented normal persistent segment tree couple times, but I'm not quite sure how to do it with Li Chao tree

»
13 days 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)