# Counting increasing subsequences with a “hacker's” Binary Index Tree

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)


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 ]

• wow, I always write list(map(; its a habit from my Python 2 days, when I would prefer map to list comprehensions. Thanks for pointing this out! Re your comment on functional programming: ya, it's just messing with state freaks me out, it's too easy to shoot yourself in the foot... – Elliot Gorokhovsky Mar 29 '17 at 3:39