LIS with segment tree on a mutable array

Revision en1, by VMaksimoski008, 2023-07-06 15:47:31

I already know how to compute the LIS of an array using a Segment Tree. I've read different materials from different sources

on how to do this, but I've never encountered how to find LIS when the array is muatble. For example, if the array was

[1, 3, 2, 10], then the leaf nodes in the Segment Tree would look like [1, 2, 2, 3].

But if we have a query (pos = 0, new_val = 12), the array would be [12, 3, 2, 10],

and the tree leaf nodes are going to be [1, 1, 1, 2].


Thanks in advance!

Tags segment tree, lis, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English VMaksimoski008 2023-07-06 15:47:31 609 Initial revision (published)