Алгоритм поиска наименьшей цены для прохода через массив

Я много думал о следующей проблеме:

Нам дан массив из n чисел. Мы начинаем с первого индекса, и наша задача — добраться до последнего индекса. При каждом шаге мы можем перейти на один или два шага вперед, и число в индексе, к которому мы переходим, представляет стоимость, которую нам нужно заплатить за посещение этого индекса. Нам нужно найти самый дешевый способ добраться до конца массива.

Например, если массив выглядит так: [2,1,4,2,5] самый дешевый способ добраться до конца — 10: мы посещаем индексы 1->2- >4->5 и мы должны заплатить 2+1+2+5 = 10, что является самым дешевым способом. Пусть f(i) будет самой низкой ценой для достижения индекса i. Это мы можем легко вычислить за время O(n) с помощью динамического программирования, поняв, что f(i) = arr[i] + min(f(i-1),f(i- 2))

Но вот в чем загвоздка: массив обновляется несколько раз, и после каждого обновления мы должны быть в состоянии определить за время O(logn), какой способ на данный момент является самым дешевым. Обновление массива происходит путем указания индекса, который будет изменен, и номера, на который он будет изменен. Например, обновление может быть следующим: arr[2] = 7, изменив наш примерный массив на [2,7,4,2,5]. Теперь самый дешевый способ будет 11.

Как мы можем поддерживать эти обновления за время O(logn)? Любые идеи?

Вот что я придумал: сначала я бы создал массив f для динамического программирования, как описано выше. Я бы сохранил содержимое этого массива в дереве сегментов s следующим образом: s(i) = f(i) - f(i-1). Это позволило бы мне обновлять интервалы f (добавляя константу к каждому значению) за время O(logn) и запрашивать значения по заданному индексу в O(logn) раз. Это может пригодиться, так как после некоторых обновлений часто бывает так, что все значения в f должны быть увеличены на константу после некоторого заданного индекса в f. Таким образом, запрашивая значение s(n) в дереве сегментов после каждого обновления, мы получим нужный нам ответ.

Однако есть разные вещи, которые могут произойти после обновления:

1. Необходимо обновить только одно значение в f. Например, если [2,1,4,2,5,4,9,3,7] изменить на [2,1,9,2,5,4,9, 3,7] нужно будет обновить только f(3), так как ни один из самых дешевых способов не проходит через индекс 3. в любом случае.
2. Все значения в f после заданного индекса должны быть обновлены константой. Для этого и подходит дерево сегментов.
3. Каждое другое значение в f после заданного индекса должно обновляться константой.
4. Что-то более случайное.