/create the lcp array from the suffix array is the input array populated from - with available pos sa is an already-computed suffix array - lcp is the resulting lcp array - *void makelcparrayvector sconst vector savector lcp int sa size)vector rankn )sn - forint ++ ranksai iint forint ++ ifranki int saranki ]whilesi =sj ++hlcpranki hifh --hfigure lcp array construction from suffix array suppose we storefor each nodethe number of nullptr links in its subtreecall this the node' weight adopt the following strategyif the left and right subtrees have weights that are not within factor of of each otherthen completely rebuild the subtree rooted at the node show the followinga we can rebuild node in ( )where is the weight of the node the algorithm has amortized cost of (log nper insertion we can rebuild node in - tree in ( log stimewhere is the weight of the node we can apply the algorithm to - treesat cost of (log nper insertion suppose we call rotatewithleftchild on an arbitrary - tree explain in detail all the reasons that the result is no longer usable - tree implement the insertion and range search for the - tree do not use recursion