Dynamic programming over interval

Question

I'm working on an algorithms problem, and I'm hitting a wall in speeding it up.

I have a function f(i,j), where i and j are integers such that 1 <= i <= j <= n for some upper bound n. This function is already written.

Furthermore, this function satisfies the equality f(i, j) + f(j, k) = f(i, k).

I need to compute f(x, y) for many different pairs x, y. Assume n is big enough that storing f(x,y) for every possible pair x,y will take up too much space.

Is there a known algorithm for this type of question? The one I'm using right now memoizes f and tries to reduce x,y to a previously computed pair of numbers by using the equality mentioned above, but my guess is that I'm not reducing in a smart way, and it's costing me time.

Edit: Assume that f(i, j) takes time proportional to j-i when computed the naive way.

Answer 1

You can use an implicit tree of power-of-two-sized intervals:

• Store f(i,i+1) for every i
• Store f(i,i+2) for every even i
• Store f(i,i+4) for every i divisible by four
• ...

There will be O(log n) tables (floor(log_2(n)), to be exact), with a total size of O(n) (~2*n).

To retrieve f(i,j) where i<=j:

• find the highest bit where i, j differ.
• Let n be the value with this bit set, and all lower bits cleared. This guarantees the following steps will always succeed:
• find f(i, n) by cutting off a chunk as large as possible from the right repeatedly
• find f(n, j) by cutting off a chunk as large as possible from the left repeatedly

The retreival accesses each table at most twice, and thus runs in O(log n).

Answer 2

The function satisfies the rule

f(i, j) + f(j, k) = f(i, k)

As you say .

So modify the function to something like f(i,j) =g(j)-g(i) , where g(i)= f(1,x)

So as

f(i,k)=g(k)-g(i)
      =g(k)-g(j)+g(j)-g(i)
      =f(j,k) + f(i,j)

So i think if you try to store all combinations of f(i,j) it is it cost you around o(n^2) space , so better you store value of g(i) values for all values of i which is of o(n) space

so when ever you need to find f(i,j) you can actually find it as g(j)-g(i) .

As

  f(i,j)= g(j)-g(i) // as we already calculated and stored the g(i) .