Будем в каждой вершине дерева отрезков хранить веса всех зверей данного поддерева. Известно, что для этого требуется O(NlogN) памяти, если N — размер исходного массива. Осталось понять, в какой структуре мы должны хранить элементы в каждой вершине.

При запросе второго типа мы просто пройдемся по всем вершинам, соответствующим данному индексу и изменим элемент в каждой из них (удалим старый, добавим новый). Значит, структура должна добавлять/удалять за O(1) или O(logN).

При запросе первого типа мы делаем запрос "два минимальных элемента на отрезке". Если мы делаем запрос на целом отрезке, то для этого достаточно посмотреть два минимума в данной вершине, иначе рекурсивно опросить левого и правого потомков. Значит, структура должна находить минимум за O(1) или O(logN).

Примером такой структуры является мультисет, сортированный по ключам. В C++ мультисет есть в стандартной библиотеке, если я не ошибаюсь; в Java его легко реализовать с помощью TreeMap.