How to make this fenwick tree LIS solution faster?

Question

Longest increasing subsequence, but with fenwick tree

Where numbers can be non unique, positive, negative and up to +/- 2^31

Hi tried a lot, and it should work. But its slow. I know that segment trees are supposed to give the O(Nlog N ) solution, but trying fenwick tree anyways.

Taking into account fenwick dont start at 0, by adding really small dummy value at beginning. Using check to see if same value is encountered before in LIS chain - must be strictly increasing.

Thanks for help

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
        self.idx = [0] * (n + 1)
        
    def update(self, indexInp, value):
        index = indexInp
        
        while index <= self.n:
            #Previous should be as close as possible
            if(value > self.tree[index] ):
                self.idx[index] = indexInp
            self.tree[index] = max(self.tree[index], value)
            index += index & -index

    def query(self, inpIndex):
        result = 0
        index = inpIndex
        idx = self.idx[index]
        
        while index > 0:
            #As close as possible
            if(self.tree[index] > result ):
                idx = self.idx[index]
                result =  self.tree[index]
                
            index -= index & -index
          
        return result, idx


def longest_increasing_subsequence_indices(values):
   
    #never considered a value smaller than all elements
    values.insert(0,min(min(values),0)-2)
    N = len(values)+1

    enumerated_list = list(enumerate(values))

    # Sort the enumerated list based on the elements (second element of each tuple)
    sorted_enumerated_list = sorted(enumerated_list, key=lambda x: x[1])

    # Extract the sorted elements and new indices
    sorted_elements = [element for _, element in sorted_enumerated_list]
    new_indices = [index for index, _ in sorted_enumerated_list]

   
    A = [0] * (N+1)
    pre = [-1] * (N+1)

    ele  = [-1] * (N+1)
    fenwick_tree = FenwickTree(N+1)
    


    for i in range(1,N):
        fenwick_tree.update(i,0)
        pre[i] = i

    lastIdx = 0
    largest = 0

    
    #For all values in list
    for val in range(1,len(values)):
    
        i = new_indices[val]

  
        #Assume no value is equal to 0
        if i-1 >= 0:
            # All values less, that is to the left, for this i
           A[i],idx =   fenwick_tree.query(i-1)
        
           pathI = idx
           alreadyFound = False
           
           #Check if path already contains this values. That is this value, and all in previous
           #best chain
           while (alreadyFound == False) and (pre[pathI] !=  pathI) and (pre[pathI] != -1):
              if(ele[pathI]  != None and values[i] == values[pathI]):
                    alreadyFound = True
              elif(ele[pathI]  != None ):
                    pathI = pre[pathI]
                    
           #Guarantees that only unique elements are in the sequence
           if(alreadyFound):
             continue
         
           A[i] = A[i] + 1
           fenwick_tree.update(i,A[i])
           
           
           pre[i] = idx
           ele[i] = i

           
           if  A[i]  > largest:
               largest =   A[i] 
               lastIdx = i
               

             
           
    indicies = []
    while pre[lastIdx] !=  lastIdx and pre[lastIdx] != -1:
        if(ele[lastIdx]  != None):
             indicies.append(ele[lastIdx]-1)
        lastIdx = pre[lastIdx]
  
    indicies.reverse() 
    return indicies
    

def main():
    try:
        while True:
            n = int(input())
            
            seq = list(map(int, input().split(" ")))
            
            lis_indices = longest_increasing_subsequence_indices(seq)
            
            print(len(lis_indices))
            print(" ".join(map(str, lis_indices)))

    except EOFError:
        pass

if __name__ == "__main__":
    main()

Answer 1

A fenwick tree should provide a fast O(n log n) solution for this problem.

I'm not sure what you're trying to do with alreadyFound, but dealing with duplicates in the array is much easier than that.

You've sorted the indexes by value, so all the indexes for the same value are grouped together in your iteration. For each group with the same value, just query all their max-left sequences first, and then add them all to the Fenwick tree.