Counting increasing subsequences with a "hacker's" Binary Index Tree

Question

This is an \$O(n \sqrt n)\$ solution to the the following problem:

Given a sequence, compute the number of non-empty increasing subsequences

The 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 sqrt
from bisect import bisect_left

def 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) 

Answer 1

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 ]