Так в разборе же всё написано. Попробую обяснить немного подробнее. В каждый момент времени у тебя есть logN объектов структур, каждый из которых имеет размер порядка 2^L, где L — порядковый номер структуры. Когда к нам пуступает запрос get — мы его перенаправляем во все экземпляры структур. Когда же запрос вида add — добавляем в структуру с номером 0. Размер структуры сразу станет  ≥ 2⁰ — мы её очищаем, а перед этим объединяем её со структурой с номером 1. Если структура с номером 1 достигла размера 2¹ — проделываем ту же процедуру, пока не получим валидные размеры структур (sizeof(struct_i) < 2ⁱ). Чем больше структура — тем реже мы будем её обновлять.
(Из разбора) Легко видеть, что каждая строка перебросится не более logm раз и на каждый запрос мы умеем отвечать за O(logm).

Об этом явно говорится в следующем абзаце там же. Попробую описать общую идею более подробно.

Пусть у нас есть некая структура, которую можно построить на N объектах за O(N) и потом с её помощью отвечать на запросы, но добавление эта структура не поддерживает. Для того, чтобы поддерживать добавление, будем хранить не одну копию структуры, а несколько, размером в различные степени двойки. Например, если N=10, у нас будут структуры размером 2 и 8.

Теперь добавление одного элемента похоже на прибавление единицы в двоичной системе счисления. Добавим в наше множество структуру размера 1, содержащую новый элемент; если в результате этого появилось две структуры размера 1, построим (за сумму размеров) структуру размера 2; если их теперь тоже две, повторим, пока требуется.

Можно показать, что это даст не более логарифма оверхеда: каждый элемент будет участвовать в построении на не более чем log n уровнях.