Представим есть задача состоящая из двух видах запроса:
1 x → Добавление числа в массив
2 x → Вывод расстояния от a[1] до первого значения X, т.е. a[k]=x, вывести k-x.
Массив после каждого запроса должен сортироваться, если это необходимо.
Как эффективно решить?
1 лайк
Допустим каждое добавление будет уникально(потому что, если это не так, то не понятно какое k выбрать, если есть два числа a[i], a[j] = x).
Задачу можно решать деревом фенвика.
Мы знаем что get(i) в дереве Фенвика возвращает нам сумму от [1, i] (or [0, i] в зависимости от реализации).
И пусть get(i) - колво чисел со значением [1, i], то тогда когда приходит запрос: 2 x
то ответ это get(x) - x, так как xтое число в массиве отсортированном будет стоять на get(x) месте.
Окей, теперь апдейты, а именно добавления чисел.
Ну нам нужно просто обновить upd(x, 1), и это прибавить +1 ко всем get(y), y >= x
Вот информация про дерево Фенвика:
https://e-maxx.ru/algo/fenwick_tree
2 лайка
т.е. операция 1 x будет выполняться за O(1), а операция 2 x будет выполняться в худшем случае O(N) верно(дерево фенвика не шарю сорян)? Если это так, то мне кажется что эт слишком долго
1 лайк
Обе операции работают за log(n). Посмотри реализацию на e maxx
1 лайк