Как найти количество элементов в std::set, меньших чем заданное K?

А чем тебя Фенвик не устроил? Удаление реализуется симметрично добавлению - только вместо того, чтобы делать +1 соотвествующему элементу, делаешь -1

Как найти количество элементов в std::set, меньших чем заданное K?

Вы не правы. std::set не обладает RandomAccess-итераторами (проще говоря, вы не можете тыкнуться в любой элемент множества за единичку, вам нужно будет итерироваться до него за О(n)), а значит, на очередной итерации бинпоиска вам придется итерироваться от его левой/правой границы до середины, что, очевидно, займет О(n) времени.