This is an \$O(n \sqrt n)\$ solution to the the following problem:Given a sequence, compute the number of non-empty increasing subsequencesThe algorithm is to compute g(i) = # of increasing subsequences that end at index i using dynamic programming, and then sum over i. A full description of the algorithm used can be found here. However, naively using dynamic programming yields an \$O(n^2)\$ solution, which is too slow. It's possible to get \$O(n \log n)\$ using a BIT, but I opted for the \$O(n \sqrt n)\$ hacker's BIT, implemented below. As I am a novice (relatively), my question is: how could I have implemented it better? Specifically, I generally prefer to program in a more functional style, but this code is very imperative. How could I have made it more functional?from math import sqrtfrom bisect import bisect_leftdef count_sequences(seq):    # Normalize seq    seq_sorted = sorted(seq)    seq = list(map(lambda x: bisect_left(seq_sorted, x), seq))    # Initialize the memoization arrays    n = len(seq); f = [0]*n    nn = int(sqrt(len(seq))); ff = [0]*(nn+2)    # Compute g(i) = f(s[i])    for s in seq:        res = sum([            1,            sum(ff[: (s // nn)]),            sum(f[(s // nn)*nn : s])        ])        f[s] += res         ff[s // nn] += res    # Sum all g(i)    return sum(ff) 
Counting increasing subsequences with a hacker's Binary Index Tree
python;programming challenge;python 3.x;tree;dynamic programming
I wouldn't go as far to say that functional programming and Python don't mix, but you should really consider what you're going for while writing it whatever language you are writing in. I would not make your goal:How could I have made it more functional?while writing Python. If you are used to writing in Haskell (for example) you shouldn't expect to always write like that in Python, so I think you should reconsider your ideal.As for an actual correction to your code:If you're going to call list on map, you might as well use a list comprehension, change:seq = list(map(lambda x: bisect_left(seq_sorted, x), seq))to:seq = [ bisect_left(seq_sorted, x) for x in seq ] 