Есть массив чисел. Как быстро отвечать на запросы

• прибавить число на отрезке
• узнать сколько раз число встречается на отрезке?

Пока что ничего быстрее не придумал.

Если кому интересно, идея sqrt-декомпозиции:

• разобьем массив на блоков
• для каждого блока будем хранить
  • cnt[x] — количество чисел x в блоке
  • delta — число, которое надо прибавить ко всем числам в этом блоке

Тогда на запрос прибавления числа D на отрезке будем отвечать так:

• Если блок полностью входит в отрезок, то изменим его delta на D

• Иначе пройдемся по элементам, которые лежат в границах запроса, и просто добавим к ним D

  cnt[a[i]] --;
  a[i] += D;
  cnt[a[i]] ++;
  

Запрос о количестве чисел X на отрезке:

• Если блок полностью входит в отрезок, просто вернем cnt[X - delta]
• Среди остальных элементов учтем те, которые равны X - delta