Algorithm for finding the lowest price to get through an array

Question

I've been thinking a lot about the following problem:

We are given an array of n numbers. We start at the first index and our task is to get to the last index. Every move we can jump one or two steps forward and the number at the index we jump to represents the cost we need to pay for visiting that index. We need to find the cheapest way for getting to the end of the array.

For example if the array looks like this: [2,1,4,2,5] the cheapest way to get to the end is 10: we visit the indexes 1->2->4->5 and we have to pay 2+1+2+5 = 10 which is the cheapest possible way. Let f(i) be the cheapest price to get to the index i. This we can calculate easily in O(n) time with dynamic programming by realizing that f(i) = arr[i] + min(f(i-1),f(i-2))

But here's the twist: The array gets updated several times and after every update we need to be able to tell in O(logn) time what is the cheapest way at the moment. Updating the array happens by telling the index which will be changed and the number it will be changed to. For example the update could be arr[2] = 7 changing our example array to [2,7,4,2,5]. Now the cheapest way would be 11.

Now how can we support these updates in O(logn) time? Any ideas?

Here's what I've come up with so far: First I would create an array f for the dynamic programming like described before. I would store the content of this array in a segment tree s in the following way: s(i) = f(i) - f(i-1). This would allow me to update intervals of f (adding a constant to every value) in O(logn) time and ask for the values at a given index in O(logn) time. This would come handy since after some updates it often happens that all the values in f would need to be increased by a constant after some given index in f. So by asking for the value of s(n) in the segment tree after every update we would get the answer we need.

There are however different things that can happen after an update:

1. Only one value in f needs to be updated. For exampe if [2,1,4,2,5,4,9,3,7] gets changed to [2,1,9,2,5,4,9,3,7] only f(3) would need to be updated, since no cheapest way went through the 3. index anyway.
2. All the values in f after a given index need to be updated by a constant. This is what the segment tree is good for.
3. Every other value in f after a given index needs to be updated by a constant.
4. Something more random.

Answer 1

Alright, I managed to solve the problem all myself so I decided to share the solution with you. :)

I was on the right track with dynamic programming and segment tree, but i was feeding the segment tree in a wrong way in my previous attempts.

Here's how we can support the updates in O(logn) time: The idea is to use a binary segment tree where the leaves of the tree represent the current array and every node stores 4 different values.

1. v1 = The lowest cost to get from the leftmost descendant to the rightmost descendant
2. v2 = The lowest cost to get from the leftmost descendant to the second rightmost descendant
3. v3 = The lowest cost to get from the second leftmost descendant to the rightmost descendant
4. v4 = The lowest cost to get from the second leftmost descendant to the second rightmost descendant

With descendants I mean the descendants of the node that are also leaves.

When updating the array we update the value at the leaf and then all its ancestors up to the root. Since at every node we already know all of these 4 values of its two children, we can calculate easily the new 4 values for the current parent node. Just to give an example: v1_current_node = min(v2_leftchild+v1_rightchild, v1_leftchild+v1_rightchild, v1_leftchild+v3_rightchild). All the other three values can be calculated in a similar way.

Since there are only O(logn) ancestors for every leaf, and all 4 values are calculated in O(1) time it takes only O(logn) time to update the entire tree.

Now that we know the 4 values for every node, we can in a similar way calculate the lowest cost from the first to the n:th node by using the nodes of the highest powers of 2 in our path in the tree that add up to n. For example if n = 11 we want to know the lowest cost from first to eleventh node and this can be done by using the information of the node that covers the leaves 1-8, the node that covers the leaves 9-10 and the leaf node 11. For all of those three nodes we know the 4 values described and we can in a similar way combine that information to figure out the answer. At very most we need to consider O(logn) nodes for doing this so that is not a problem.