Comments 4
Первый вид - это замена конкретного элемента на другой.
Не только одного. Можно замену сделать и на отрезке, причем за тот же логарифм (при таком запросе не делается "поштучное" обновление самих элементов - данные "застревают" на промежуточных уровнях дерева, и далее возможны разные стратегии). Подробности, например, тут - https://e-maxx.ru/algo/segment_tree
Можно не дополнять массив нулями (или нейтральными элементами). Надо только правильно подсчитать, сколько надо промежуточных элементов. Как бы представить, что массив дополнен, но размер его не менять. Т.к. эти виртуальные элементы находятся в конце их можно игнорировать. Правда, надо будет учитывать, что у вершины может быть только левый ребенок. При итеративной реализации снизу — код вообще точно такой же.
Еще, индексировать можно и с 0. Тогда просто формулы чуть-чуть меняются: 2*x+1, 2*x+2 для детей и (x-1)/2 для отца.
Можно писать рекурсивное до с памятью в 2N простой перенумерацией детей в порядке эйлерова обхода. Конкретнее можно глянуть на англ емаксе.
Понимаем обычное дерево отрезков